oj.uz

Submission #49609

# Submission time Handle Problem Language Result Execution time Memory
49609 2018-06-01T02:03:03 Z yogahmad Simurgh (IOI17_simurgh) C++14
0 / 100
 204 ms 18612 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];
}
bool benar[mx];
int par[mx];
int find(int aa){
	if(aa==par[aa])return aa;
	return par[aa]=find(par[aa]);
}
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;
	}
	for(int i=1;i<=N;i++){
		random_shuffle(ALL(g[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);
	int cnt=0;
	cnt++;
//	debug(maks);
	for(auto i:cycle){
	//	cout<<i.f-1<<" -> "<<i.s-1<<endl;
		int dari=i.f,ke=i.s,sampai=-1;
		int besar=0;
		while(dari!=ke){
		//	cout<<"ini "<<" "<<dari-1<<" "<<P[dari]-1<<endl;
			if(di[brp[dari][P[dari]]]!=-1 && !benar[brp[dari][P[dari]]]){
				if(cnt==30000)
					break;
				int tmp=brp[dari][P[dari]];
				r[di[tmp]]=brp[i.f][i.s];
				for(int j=0;j<N;j++)
					par[j]=j;
				bool ya=true;
				for(int i:r){
					int x=find(u[i]);
					int y=find(v[i]);
					if(x==y){
						ya=false;
						break;
					}
					par[x]=y;
				}
				int sem=0;
				if(ya && cnt<30000){
					cnt++;
					sem=count_common_roads(r);
					if(sem==maks-1){
						r[di[tmp]]=brp[dari][P[dari]];
						benar[tmp]=true;
						break;
					}
				}
			//	debug(sem);
				if(sem>besar){
					satu=r;
					besar=sem;
				}
				r[di[tmp]]=brp[dari][P[dari]];
				if(besar>maks){
					sampai=dari;
					break;
				}
			}
			dari=P[dari];
		}
		if(sampai!=-1){
			dari=i.f;
			while(dari!=sampai){
				if(di[brp[dari][P[dari]]]!=-1)benar[brp[dari][P[dari]]]=true;
				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;
			}
		}
		if(cnt==30000)
			break;
	//	for(int i:r)cout<<i<<' ';
	//	cout<<endl;
	//	debug(maks);
	}
	assert(maks==N-1);
//	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:59:10: warning: unused variable 'i' [-Wunused-variable]
  for(int i:r){
          ^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7160 KB correct
2 Correct 9 ms 7396 KB correct
3 Correct 7 ms 7396 KB correct
4 Correct 7 ms 7396 KB correct
5 Correct 7 ms 7396 KB correct
6 Correct 7 ms 7408 KB correct
7 Correct 7 ms 7408 KB correct
8 Correct 7 ms 7408 KB correct
9 Correct 7 ms 7552 KB correct
10 Correct 8 ms 7552 KB correct
11 Correct 8 ms 7552 KB correct
12 Correct 8 ms 7552 KB correct
13 Runtime error 17 ms 14564 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7160 KB correct
2 Correct 9 ms 7396 KB correct
3 Correct 7 ms 7396 KB correct
4 Correct 7 ms 7396 KB correct
5 Correct 7 ms 7396 KB correct
6 Correct 7 ms 7408 KB correct
7 Correct 7 ms 7408 KB correct
8 Correct 7 ms 7408 KB correct
9 Correct 7 ms 7552 KB correct
10 Correct 8 ms 7552 KB correct
11 Correct 8 ms 7552 KB correct
12 Correct 8 ms 7552 KB correct
13 Runtime error 17 ms 14564 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7160 KB correct
2 Correct 9 ms 7396 KB correct
3 Correct 7 ms 7396 KB correct
4 Correct 7 ms 7396 KB correct
5 Correct 7 ms 7396 KB correct
6 Correct 7 ms 7408 KB correct
7 Correct 7 ms 7408 KB correct
8 Correct 7 ms 7408 KB correct
9 Correct 7 ms 7552 KB correct
10 Correct 8 ms 7552 KB correct
11 Correct 8 ms 7552 KB correct
12 Correct 8 ms 7552 KB correct
13 Runtime error 17 ms 14564 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14564 KB correct
2 Correct 8 ms 14564 KB correct
3 Incorrect 204 ms 18612 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7160 KB correct
2 Correct 9 ms 7396 KB correct
3 Correct 7 ms 7396 KB correct
4 Correct 7 ms 7396 KB correct
5 Correct 7 ms 7396 KB correct
6 Correct 7 ms 7408 KB correct
7 Correct 7 ms 7408 KB correct
8 Correct 7 ms 7408 KB correct
9 Correct 7 ms 7552 KB correct
10 Correct 8 ms 7552 KB correct
11 Correct 8 ms 7552 KB correct
12 Correct 8 ms 7552 KB correct
13 Runtime error 17 ms 14564 KB Execution killed with signal 11 (could be triggered by violating memory limits)