oj.uz

답안 #49545

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49545 2018-05-31T03:18:34 Z yogahmad Simurgh (IOI17_simurgh) C++14
0 / 100
 9 ms 7396 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 cnt=0;
	cnt++;
	int maks=count_common_roads(r);
//	for(int i:r)cout<<i<<" ";
//	cout<<endl;
//	cout<<maks<<endl;
	sort(ALL(cycle),cmp);
//	debug(maks);
	for(auto i:cycle){
	//	cout<<i.f<<" -> "<<i.s<<endl;
		int dari=i.f,ke=i.s;
		int besar=0;
		while(dari!=ke){
		//	if(dari)cout<<"ini "<<brp[dari][P[dari]]<<" "<<dari<<" "<<P[dari]<<endl;
			if(di[brp[dari][P[dari]]]!=-1){
				int tmp=brp[dari][P[dari]];
				r[di[tmp]]=brp[i.f][i.s];
				if(cnt==30000)
					break;
				cnt++;
				int 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);
	}
	assert(maks==N-1);
//	cout<<maks<<endl;
	return r;
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 7160 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 7160 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 7160 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7396 KB correct
2 Incorrect 9 ms 7396 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 7160 KB WA in grader: NO
2 Halted 0 ms 0 KB -