CF 240E, 一些意外状况.
这个题在Codeforces上是比较弱的……所以在CF上AC不一定是对的……
我现在在造这个题的数据……然后用了一些奇怪的方法gen数据……
然后发现某种姿势下我的朱刘/Edmonds会MLE……
然后为了获得正确的out在CF上拉了几段AC代码然后跑出了不同的out……
我造了一个比较小的数据是这样的:
1000 3983 1 2 1 2 3 1 3 4 1 4 5 1 ...... 997 998 1 998 999 1 999 1000 1 4 1 0 5 2 0 6 3 0 ...... 997 994 0 998 995 0 999 996 0 1000 997 0 7 1 0 8 2 0 9 3 0 10 4 0 ...... 998 992 0 999 993 0 1000 994 0 8 1 0 9 2 0 10 3 0 ...... 997 990 0 998 991 0 999 992 0 1000 993 0
它是用这段程序生成的:
// Author: Ruchiose #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #define i64 long long #define d64 long double #define fortodo(i, f, t) for (i = f; i <= t; i++) using namespace std; int main() { int N = 1000; printf("%d %d\n", N, N * 4 - 17); int i; fortodo(i, 1, N - 1) printf("%d %d 1\n", i, i + 1); fortodo(i, 1, N - 3) printf("%d %d 0\n", i + 3, i); fortodo(i, 1, N - 6) printf("%d %d 0\n", i + 6, i); fortodo(i, 1, N - 7) printf("%d %d 0\n", i + 7, i); }
显然,为了从1到达i必须要先到达i-1,因此后3N-16条边都是没用的,答案应该是修复所有需要修复的边。
下面是拉来的一些AC代码的输出:
-1
3 997 998 999
-1
999 629 2514 2515 2516 2517 2518 2519 2520 25......
-1
999 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17......
999 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17......
(似乎-1会被代码高亮君吃掉囧)
看起来只有jiry_2和sone的程序可以跑出正常的结果。
可是这两个程序里面M开了200万,而这样的数据似乎会让空间开销到N^2级别……
然后N取5000的时候这两个程序已经输出-1了。
然后我已经找不到可以确定是正确的程序了……
(杜教:你可以去学习一下O(MlogN)的写法)
所以这个姿势的数据就只能放到N=1000……感到非常囧。
关于这两个程序在其它姿势gen的数据里是否和我的程序一样还没有测试……因为spj还没写……
多半最后是拿这三个程序的众数造out了囧。
UPD:
数据&SPJ已造。我的7915842造出的数据,sone的7184472和jiry的8162109都AC了(tsinsen: 978615&978616)。
大概是随机数据很弱的原因,Stilwell的5485603和vfk的2406412通过了除了#12以外的所有测试点(tsinsen: 978619&978623)。
其中#12就是上面构造的那个数据。那么感觉这题的数据应该是没有问题了。如有问题请联系我。
Aug 30, 2021 12:06:24 AM
In this case you will begin it is important, it again produces a web site a strong significant internet site:
Sep 25, 2021 05:15:32 AM
In this particular article, you will see a summary, satisfy browse this post.