oj.uz

Submission #59535

# Submission time Handle Problem Language Result Execution time Memory
59535 2018-07-22T09:20:19 Z WA_TLE Game (IOI14_game) C++14
42 / 100
 1000 ms 56108 KB 
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=998244353;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
#include"game.h"
int n;
int hen[1500][1500]={0};//直接の辺 -1->No 0->未定 1->想定解 2->Yes
vector<int>kno;//可能性のある辺
mt19937 engine(13333);
vector<int>rng;
//O(n^2logn?) 自信がない
//まずランダムな想定解を作る
//想定解にかかってないなら無条件にNoを返していい
//想定解にかかったなら想定解を変える
vector<vector<int>>ki;
void initialize(int in){
	n=in;
	//uとvをランダムに置き換える
	rng.res(n);
	int i,j;
	for(i=0;i<n;i++){rng[i]=i;}
	shuffle(rng.begin(),rng.end(),engine);
	//想定解を作る
	vector<bool>use(n);
	use[0]=true;
	int gen=0,oto=1;
	ki.res(n);
	while(oto<n){
		int ne=engine()%n;
		if(use[ne]){gen=ne;}
		else{ki[gen].pub(ne);ki[ne].pub(gen);hen[gen][ne]=1;hen[ne][gen]=1;gen=ne;use[ne]=1;oto++;}
	}
	/*kno.res(n);
	for(i=0;i<n;i++){
		kno[i].res(n-1);
		for(j=1;j<n;j++){kno[i][j-1]=(i+j)%n;}
	}*/
}
int hasEdge(int u,int v){
	int i,j;
	u=rng[u];
	v=rng[v];
	if(hen[u][v]==0){hen[u][v]=-1;hen[v][u]=-1;return 0;}
	vector<bool>doti(n);
	doti[u]=1;
	queue<int>que;que.push(u);
	while(que.size()>0){
		int t=que.front();que.pop();
		for(auto it:ki[t]){
			if(doti[it]){continue;}
			if(it==v){continue;}
			doti[it]=1;
			que.push(it);
		}
	}
	vector<int>ulis;
	vector<int>vlis;
	for(i=0;i<n;i++){if(doti[i]){ulis.pub(i);}else{vlis.pub(i);}}
	shuffle(ulis.begin(),ulis.end(),engine);
	shuffle(vlis.begin(),vlis.end(),engine);
	int au=-1,av=-1;
	for(i=0;i<ulis.size();i++){
		for(j=0;j<vlis.size();j++){
			int gu=ulis[i];
			int gv=vlis[(i+j)%vlis.size()];
			if(gu==u&&gv==v){continue;}
			if(hen[gu][gv]>=0){au=gu;av=gv;break;}
		}
		if(au!=-1){break;}
	}
	if(au==-1){hen[u][v]=2;hen[v][u]=2;return 1;}
	hen[u][v]=-1;hen[v][u]=-1;
	hen[au][av]=-1;hen[av][au]=-1;
	for(i=0;i<ki[u].size();i++){
		if(ki[u][i]==v){ki[u][i]=ki[u].back();ki[u].pob();}
	}
	for(i=0;i<ki[v].size();i++){
		if(ki[v][i]==u){ki[v][i]=ki[v].back();ki[v].pob();}
	}
	ki[au].pub(av);
	ki[av].pub(au);
	return 0;
}

Compilation message

game.cpp: In function 'void initialize(int)':
game.cpp:67:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
game.cpp: In function 'int hasEdge(int, int)':
game.cpp:109:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<ulis.size();i++){
          ~^~~~~~~~~~~~
game.cpp:110:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<vlis.size();j++){
           ~^~~~~~~~~~~~
game.cpp:121:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<ki[u].size();i++){
          ~^~~~~~~~~~~~~
game.cpp:124:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<ki[v].size();i++){
          ~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 480 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 3 ms 560 KB Output is correct
6 Correct 3 ms 564 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 3 ms 572 KB Output is correct
9 Correct 2 ms 672 KB Output is correct
10 Correct 3 ms 672 KB Output is correct
11 Correct 3 ms 672 KB Output is correct
12 Correct 3 ms 672 KB Output is correct
13 Correct 3 ms 672 KB Output is correct
14 Correct 3 ms 672 KB Output is correct
15 Correct 2 ms 676 KB Output is correct
16 Correct 2 ms 680 KB Output is correct
17 Correct 3 ms 684 KB Output is correct
18 Correct 3 ms 688 KB Output is correct
19 Correct 3 ms 688 KB Output is correct
20 Correct 3 ms 688 KB Output is correct
21 Correct 2 ms 700 KB Output is correct
22 Correct 3 ms 704 KB Output is correct
23 Correct 3 ms 708 KB Output is correct
24 Correct 3 ms 712 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 720 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 732 KB Output is correct
6 Correct 2 ms 736 KB Output is correct
7 Correct 3 ms 740 KB Output is correct
8 Correct 3 ms 744 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 2 ms 748 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 2 ms 764 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 3 ms 772 KB Output is correct
16 Correct 2 ms 776 KB Output is correct
17 Correct 3 ms 908 KB Output is correct
18 Correct 3 ms 908 KB Output is correct
19 Correct 3 ms 908 KB Output is correct
20 Correct 3 ms 908 KB Output is correct
21 Correct 2 ms 908 KB Output is correct
22 Correct 3 ms 908 KB Output is correct
23 Correct 3 ms 908 KB Output is correct
24 Correct 2 ms 908 KB Output is correct
25 Correct 5 ms 956 KB Output is correct
26 Correct 3 ms 960 KB Output is correct
27 Correct 4 ms 960 KB Output is correct
28 Correct 3 ms 968 KB Output is correct
29 Correct 3 ms 968 KB Output is correct
30 Correct 3 ms 1052 KB Output is correct
31 Correct 3 ms 1052 KB Output is correct
32 Correct 4 ms 1052 KB Output is correct
33 Correct 4 ms 1052 KB Output is correct
34 Correct 8 ms 1480 KB Output is correct
35 Correct 6 ms 1480 KB Output is correct
36 Correct 9 ms 1480 KB Output is correct
37 Correct 8 ms 1480 KB Output is correct
38 Correct 7 ms 1480 KB Output is correct
39 Correct 6 ms 1480 KB Output is correct
40 Correct 7 ms 1532 KB Output is correct
41 Correct 8 ms 1532 KB Output is correct
42 Correct 7 ms 1532 KB Output is correct
43 Correct 8 ms 1532 KB Output is correct
44 Correct 7 ms 1532 KB Output is correct
45 Correct 8 ms 1532 KB Output is correct
46 Correct 7 ms 1552 KB Output is correct
47 Correct 7 ms 1700 KB Output is correct
48 Correct 7 ms 1700 KB Output is correct
49 Correct 7 ms 1700 KB Output is correct
50 Correct 9 ms 1700 KB Output is correct
51 Correct 6 ms 1700 KB Output is correct
52 Correct 6 ms 1700 KB Output is correct
53 Correct 9 ms 1700 KB Output is correct
54 Correct 8 ms 1712 KB Output is correct

Subtask #3
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1712 KB Output is correct
2 Correct 3 ms 1712 KB Output is correct
3 Correct 3 ms 1712 KB Output is correct
4 Correct 3 ms 1712 KB Output is correct
5 Correct 3 ms 1712 KB Output is correct
6 Correct 3 ms 1712 KB Output is correct
7 Correct 3 ms 1712 KB Output is correct
8 Correct 4 ms 1712 KB Output is correct
9 Correct 3 ms 1712 KB Output is correct
10 Correct 3 ms 1712 KB Output is correct
11 Correct 2 ms 1712 KB Output is correct
12 Correct 2 ms 1712 KB Output is correct
13 Correct 2 ms 1712 KB Output is correct
14 Correct 3 ms 1712 KB Output is correct
15 Correct 5 ms 1712 KB Output is correct
16 Correct 3 ms 1712 KB Output is correct
17 Correct 3 ms 1712 KB Output is correct
18 Correct 3 ms 1712 KB Output is correct
19 Correct 3 ms 1712 KB Output is correct
20 Correct 2 ms 1712 KB Output is correct
21 Correct 3 ms 1712 KB Output is correct
22 Correct 3 ms 1712 KB Output is correct
23 Correct 3 ms 1712 KB Output is correct
24 Correct 3 ms 1712 KB Output is correct
25 Correct 4 ms 1712 KB Output is correct
26 Correct 4 ms 1712 KB Output is correct
27 Correct 3 ms 1712 KB Output is correct
28 Correct 3 ms 1712 KB Output is correct
29 Correct 4 ms 1712 KB Output is correct
30 Correct 3 ms 1712 KB Output is correct
31 Correct 3 ms 1712 KB Output is correct
32 Correct 3 ms 1712 KB Output is correct
33 Correct 3 ms 1712 KB Output is correct
34 Correct 7 ms 1864 KB Output is correct
35 Correct 7 ms 1884 KB Output is correct
36 Correct 7 ms 1904 KB Output is correct
37 Correct 7 ms 1924 KB Output is correct
38 Correct 9 ms 1944 KB Output is correct
39 Correct 8 ms 1964 KB Output is correct
40 Correct 8 ms 1984 KB Output is correct
41 Correct 6 ms 2008 KB Output is correct
42 Correct 7 ms 2024 KB Output is correct
43 Correct 8 ms 2156 KB Output is correct
44 Correct 8 ms 2156 KB Output is correct
45 Correct 8 ms 2156 KB Output is correct
46 Correct 8 ms 2156 KB Output is correct
47 Correct 9 ms 2156 KB Output is correct
48 Correct 7 ms 2156 KB Output is correct
49 Correct 8 ms 2164 KB Output is correct
50 Correct 7 ms 2184 KB Output is correct
51 Correct 6 ms 2204 KB Output is correct
52 Correct 10 ms 2224 KB Output is correct
53 Correct 6 ms 2244 KB Output is correct
54 Correct 9 ms 2248 KB Output is correct
55 Correct 274 ms 6892 KB Output is correct
56 Correct 237 ms 7880 KB Output is correct
57 Correct 218 ms 8588 KB Output is correct
58 Correct 238 ms 9820 KB Output is correct
59 Correct 209 ms 10668 KB Output is correct
60 Correct 261 ms 11536 KB Output is correct
61 Correct 243 ms 12692 KB Output is correct
62 Correct 258 ms 13468 KB Output is correct
63 Correct 191 ms 14444 KB Output is correct
64 Correct 154 ms 15420 KB Output is correct
65 Correct 166 ms 16488 KB Output is correct
66 Correct 322 ms 17504 KB Output is correct
67 Correct 324 ms 18560 KB Output is correct
68 Correct 232 ms 19332 KB Output is correct
69 Correct 316 ms 20428 KB Output is correct
70 Correct 302 ms 21276 KB Output is correct
71 Correct 187 ms 22380 KB Output is correct
72 Correct 301 ms 23372 KB Output is correct
73 Correct 234 ms 24204 KB Output is correct
74 Correct 292 ms 25308 KB Output is correct
75 Correct 275 ms 26296 KB Output is correct
76 Correct 615 ms 31100 KB Output is correct
77 Correct 593 ms 33500 KB Output is correct
78 Correct 635 ms 35644 KB Output is correct
79 Correct 568 ms 37916 KB Output is correct
80 Correct 579 ms 40176 KB Output is correct
81 Correct 647 ms 42356 KB Output is correct
82 Correct 608 ms 44732 KB Output is correct
83 Correct 533 ms 46888 KB Output is correct
84 Correct 690 ms 49148 KB Output is correct
85 Execution timed out 1063 ms 56108 KB Time limit exceeded
86 Halted 0 ms 0 KB -