oj.uz

Submission #49600

# Submission time Handle Problem Language Result Execution time Memory
49600 2018-06-01T01:34:48 Z yogahmad Simurgh (IOI17_simurgh) C++14
30 / 100
 3000 ms 12640 KB 
#include <bits/stdc++.h>
#include "simurgh.h"
#define f first
#define s second
#define pb push_back
#define mx 250003
#define ALL(x) x.begin(),x.end()
using namespace std;
int di[mx],M,idx,brp[505][505],level[mx];
bool sudah[mx];
int P[mx];
vector<pair<int,int>>cycle;
vector<int> r;
vector<int>g[mx];


void dfs(int now,int par=0,int lev=1){
	sudah[now]=true;
	level[now]=lev;
	for(auto i:g[now]){
		if(i==par)
			continue;
		if(!sudah[i]){
			P[i]=now;
			di[brp[now][i]]=idx++;
			r.pb(brp[now][i]);
			dfs(i,now,lev+1);
		}
		else if(level[i]<level[now]){
			cycle.pb({now,i});
		}
	}
}

bool cmp(pair<int,int>x,pair<int,int>y){
	return level[x.s]>level[y.s];
}

vector<int> find_roads(int N, vector<int> u, vector<int> v) {
	M=u.size();
	for(int i=0;i<M;i++){
		g[u[i]+1].pb(v[i]+1);
		g[v[i]+1].pb(u[i]+1);
		brp[u[i]+1][v[i]+1]=i;
		brp[v[i]+1][u[i]+1]=i;
	}
	memset(di,-1,sizeof di);
	dfs(1,0);
	vector<int>satu(N-1);
	int maks=count_common_roads(r);
	for(int i:r){
	//	cout<<u[i]<<" -> "<<v[i]<<"  --  "<<i<<endl;
	}
//	cout<<maks<<endl;
	sort(ALL(cycle),cmp);
//	debug(maks);
	for(auto i:cycle){
	//	cout<<i.f-1<<" -> "<<i.s-1<<endl;
		int dari=i.f,ke=i.s;
		int besar=0;
		while(dari!=ke){
		//	cout<<"ini "<<" "<<dari-1<<" "<<P[dari]-1<<endl;
			if(di[brp[dari][P[dari]]]!=-1){
				int tmp=brp[dari][P[dari]];
				r[di[tmp]]=brp[i.f][i.s];
				for(int j=0;j<N;j++)
					sudah[j]=false;
				queue<int>q;
				q.push(0);
				sudah[0]=true;
				while(!q.empty()){
					int now=q.front();
					q.pop();
					for(int i=0;i<N-1;i++){
						if(u[r[i]]==now && !sudah[v[r[i]]]){
							q.push(v[r[i]]);
							sudah[v[r[i]]]=true;
						}
						if(v[r[i]]==now && !sudah[u[r[i]]]){
							q.push(u[r[i]]);
							sudah[u[r[i]]]=true;
						}
					}
				}
				bool ya=true;
				for(int j=0;j<N;j++){
					if(!sudah[j]){
						ya=false;
					}
				}
				int sem=0;
				if(ya)sem=count_common_roads(r);
			//	debug(sem);
				if(sem>besar){
					satu=r;
					besar=sem;
				}
				r[di[tmp]]=brp[dari][P[dari]];
			}
			dari=P[dari];
		}
		if(besar>maks){
			maks=besar;
			r=satu;
			memset(di,-1,sizeof di);
			for(int i=0;i<N-1;i++){
				di[r[i]]=i;
			}
		}
	//	for(int i:r)cout<<i<<' ';
	//	cout<<endl;
	//	debug(maks);
	}
//	cout<<maks<<endl;
	return r;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:51:10: warning: unused variable 'i' [-Wunused-variable]
  for(int i:r){
          ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7160 KB correct
2 Correct 8 ms 7276 KB correct
3 Correct 9 ms 7332 KB correct
4 Correct 8 ms 7332 KB correct
5 Correct 9 ms 7332 KB correct
6 Correct 9 ms 7388 KB correct
7 Correct 10 ms 7440 KB correct
8 Correct 8 ms 7440 KB correct
9 Correct 9 ms 7500 KB correct
10 Correct 9 ms 7500 KB correct
11 Correct 10 ms 7500 KB correct
12 Correct 8 ms 7500 KB correct
13 Correct 9 ms 7500 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7160 KB correct
2 Correct 8 ms 7276 KB correct
3 Correct 9 ms 7332 KB correct
4 Correct 8 ms 7332 KB correct
5 Correct 9 ms 7332 KB correct
6 Correct 9 ms 7388 KB correct
7 Correct 10 ms 7440 KB correct
8 Correct 8 ms 7440 KB correct
9 Correct 9 ms 7500 KB correct
10 Correct 9 ms 7500 KB correct
11 Correct 10 ms 7500 KB correct
12 Correct 8 ms 7500 KB correct
13 Correct 9 ms 7500 KB correct
14 Correct 60 ms 7524 KB correct
15 Correct 74 ms 7532 KB correct
16 Correct 87 ms 7680 KB correct
17 Correct 46 ms 7680 KB correct
18 Correct 23 ms 7680 KB correct
19 Correct 49 ms 7832 KB correct
20 Correct 36 ms 7832 KB correct
21 Correct 51 ms 7832 KB correct
22 Correct 44 ms 7832 KB correct
23 Correct 35 ms 7832 KB correct
24 Correct 65 ms 7832 KB correct
25 Correct 9 ms 7832 KB correct
26 Correct 34 ms 7832 KB correct
27 Correct 48 ms 7884 KB correct
28 Correct 13 ms 7884 KB correct
29 Correct 10 ms 7884 KB correct
30 Correct 56 ms 7920 KB correct
31 Correct 56 ms 7972 KB correct
32 Correct 65 ms 7972 KB correct
33 Correct 59 ms 7972 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7160 KB correct
2 Correct 8 ms 7276 KB correct
3 Correct 9 ms 7332 KB correct
4 Correct 8 ms 7332 KB correct
5 Correct 9 ms 7332 KB correct
6 Correct 9 ms 7388 KB correct
7 Correct 10 ms 7440 KB correct
8 Correct 8 ms 7440 KB correct
9 Correct 9 ms 7500 KB correct
10 Correct 9 ms 7500 KB correct
11 Correct 10 ms 7500 KB correct
12 Correct 8 ms 7500 KB correct
13 Correct 9 ms 7500 KB correct
14 Correct 60 ms 7524 KB correct
15 Correct 74 ms 7532 KB correct
16 Correct 87 ms 7680 KB correct
17 Correct 46 ms 7680 KB correct
18 Correct 23 ms 7680 KB correct
19 Correct 49 ms 7832 KB correct
20 Correct 36 ms 7832 KB correct
21 Correct 51 ms 7832 KB correct
22 Correct 44 ms 7832 KB correct
23 Correct 35 ms 7832 KB correct
24 Correct 65 ms 7832 KB correct
25 Correct 9 ms 7832 KB correct
26 Correct 34 ms 7832 KB correct
27 Correct 48 ms 7884 KB correct
28 Correct 13 ms 7884 KB correct
29 Correct 10 ms 7884 KB correct
30 Correct 56 ms 7920 KB correct
31 Correct 56 ms 7972 KB correct
32 Correct 65 ms 7972 KB correct
33 Correct 59 ms 7972 KB correct
34 Execution timed out 3031 ms 9532 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9532 KB correct
2 Correct 9 ms 9532 KB correct
3 Execution timed out 3038 ms 12640 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7160 KB correct
2 Correct 8 ms 7276 KB correct
3 Correct 9 ms 7332 KB correct
4 Correct 8 ms 7332 KB correct
5 Correct 9 ms 7332 KB correct
6 Correct 9 ms 7388 KB correct
7 Correct 10 ms 7440 KB correct
8 Correct 8 ms 7440 KB correct
9 Correct 9 ms 7500 KB correct
10 Correct 9 ms 7500 KB correct
11 Correct 10 ms 7500 KB correct
12 Correct 8 ms 7500 KB correct
13 Correct 9 ms 7500 KB correct
14 Correct 60 ms 7524 KB correct
15 Correct 74 ms 7532 KB correct
16 Correct 87 ms 7680 KB correct
17 Correct 46 ms 7680 KB correct
18 Correct 23 ms 7680 KB correct
19 Correct 49 ms 7832 KB correct
20 Correct 36 ms 7832 KB correct
21 Correct 51 ms 7832 KB correct
22 Correct 44 ms 7832 KB correct
23 Correct 35 ms 7832 KB correct
24 Correct 65 ms 7832 KB correct
25 Correct 9 ms 7832 KB correct
26 Correct 34 ms 7832 KB correct
27 Correct 48 ms 7884 KB correct
28 Correct 13 ms 7884 KB correct
29 Correct 10 ms 7884 KB correct
30 Correct 56 ms 7920 KB correct
31 Correct 56 ms 7972 KB correct
32 Correct 65 ms 7972 KB correct
33 Correct 59 ms 7972 KB correct
34 Execution timed out 3031 ms 9532 KB Time limit exceeded
35 Halted 0 ms 0 KB -