oj.uz

Submission #600470

# Submission time Handle Problem Language Result Execution time Memory
600470 2022-07-20T22:16:25 Z StrawHatWess Simurgh (IOI17_simurgh) C++17
0 / 100
 3000 ms 340 KB 
#include "simurgh.h"

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
#define FOR(i,a,b) for(int i=a; i<b; i++)
typedef vector<int>vi; 
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x) 
typedef pair<ll,ll>pi;
typedef vector<pi>vpi; 
#define fi first
#define se second

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const ll INF=1e18; 

//---------------------------------------------------------

const int MX=500+10; 

vi p(MX); 
int findSet(int u){return p[u]==u? u: p[u]=findSet(p[u]);}

vi rnk(MX); 
void unionSet(int u, int v){
	u=findSet(u); v=findSet(v); 

	if(rnk[u]<rnk[v]) swap(u,v);
	if(rnk[u]==rnk[v]) rnk[u]++; 

	p[v]=u; 
}

//----------------

int N,M; 
vi U,V; 
map<int,int>ed[MX]; 

vi a,b; 

vi adj[MX]; 
void build(){
	FOR(i,0,N) adj[i].clear();

	for(int i: a){
		int u=U[i], v=V[i]; 
		adj[u].pb(v); adj[v].pb(u); 
	}
}


vi par(MX); 
void dfs(int u, int p){
	par[u]=p; 
	for(int v: adj[u]) if(v!=p) dfs(v,u); 
}

vi find_roads(int n, vi U, vi V) {
	N=n; M=sz(U); 
	::U=U; ::V=V; 

	FOR(i,0,N) p[i]=i,rnk[i]=0; 
	
	
	FOR(i,0,M){
		int u=U[i], v=V[i]; 
		ed[u][v]=ed[v][u]=i; 

		if(findSet(u)!=findSet(v)) unionSet(u,v), a.pb(i); 
		else b.pb(i);
	}

	vi val(M,-1); 

	int X=count_common_roads(a);
	for(int i: b){
		int u=U[i], v=V[i];

		build(); //build tree
		dfs(u,u);

		vi vec; 

		while(v!=u){
			int vp=par[v]; 

			//considering edge vp-v
			int j=ed[v][vp]; 
			if(val[j]==1) continue; 

			vi ap=a; 
			for(int &it: ap) if(it==j) it=i; 
			int Y=count_common_roads(ap); 

			if(X>Y){
				val[i]=0; 
				val[j]=1; 
				break; 
			}
			else if(X<Y){
				val[j]=0; 
				val[i]=1;
				a=ap;  
				break; 
			}
			else{
				vec.pb(j);
			}

			v=vp;
		}

		if(val[i]==-1) val[i]=0;
		for(int j: vec) val[j]=val[i]; 
	}

	return a; 
}


/*

4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5


*/

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB correct
2 Execution timed out 3060 ms 340 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -