oj.uz

Submission #600459

# Submission time Handle Problem Language Result Execution time Memory
600459 2022-07-20T21:53:40 Z StrawHatWess Simurgh (IOI17_simurgh) C++17
30 / 100
 192 ms 10636 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);
	}

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

		build(); //build tree
		dfs(u,u);
		while(v!=u){
			int vp=par[v]; 

			//considering edge vp-v
			int j=ed[v][vp]; 
			for(int &it: a) if(it==j) it=i; 

			if(!ckmax(X,count_common_roads(a))){
				for(int &it: a) if(it==i) it=j;
			}
			else break;  

			v=vp;
		}
	}

	return a; 
}


/*

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


*/

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 0 ms 340 KB correct
3 Correct 0 ms 344 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 1 ms 340 KB correct
6 Correct 1 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 344 KB correct
9 Correct 0 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 0 ms 340 KB correct
3 Correct 0 ms 344 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 1 ms 340 KB correct
6 Correct 1 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 344 KB correct
9 Correct 0 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct
14 Correct 12 ms 504 KB correct
15 Correct 7 ms 508 KB correct
16 Correct 7 ms 504 KB correct
17 Correct 11 ms 472 KB correct
18 Correct 4 ms 340 KB correct
19 Correct 10 ms 472 KB correct
20 Correct 8 ms 468 KB correct
21 Correct 8 ms 340 KB correct
22 Correct 5 ms 340 KB correct
23 Correct 6 ms 344 KB correct
24 Correct 4 ms 340 KB correct
25 Correct 1 ms 340 KB correct
26 Correct 4 ms 340 KB correct
27 Correct 5 ms 340 KB correct
28 Correct 2 ms 340 KB correct
29 Correct 1 ms 340 KB correct
30 Correct 7 ms 468 KB correct
31 Correct 7 ms 340 KB correct
32 Correct 8 ms 432 KB correct
33 Correct 7 ms 428 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 0 ms 340 KB correct
3 Correct 0 ms 344 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 1 ms 340 KB correct
6 Correct 1 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 344 KB correct
9 Correct 0 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct
14 Correct 12 ms 504 KB correct
15 Correct 7 ms 508 KB correct
16 Correct 7 ms 504 KB correct
17 Correct 11 ms 472 KB correct
18 Correct 4 ms 340 KB correct
19 Correct 10 ms 472 KB correct
20 Correct 8 ms 468 KB correct
21 Correct 8 ms 340 KB correct
22 Correct 5 ms 340 KB correct
23 Correct 6 ms 344 KB correct
24 Correct 4 ms 340 KB correct
25 Correct 1 ms 340 KB correct
26 Correct 4 ms 340 KB correct
27 Correct 5 ms 340 KB correct
28 Correct 2 ms 340 KB correct
29 Correct 1 ms 340 KB correct
30 Correct 7 ms 468 KB correct
31 Correct 7 ms 340 KB correct
32 Correct 8 ms 432 KB correct
33 Correct 7 ms 428 KB correct
34 Incorrect 192 ms 4028 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Correct 1 ms 340 KB correct
3 Incorrect 182 ms 10636 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB correct
2 Correct 0 ms 340 KB correct
3 Correct 0 ms 344 KB correct
4 Correct 1 ms 340 KB correct
5 Correct 1 ms 340 KB correct
6 Correct 1 ms 340 KB correct
7 Correct 1 ms 340 KB correct
8 Correct 1 ms 344 KB correct
9 Correct 0 ms 340 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 0 ms 340 KB correct
12 Correct 1 ms 340 KB correct
13 Correct 1 ms 340 KB correct
14 Correct 12 ms 504 KB correct
15 Correct 7 ms 508 KB correct
16 Correct 7 ms 504 KB correct
17 Correct 11 ms 472 KB correct
18 Correct 4 ms 340 KB correct
19 Correct 10 ms 472 KB correct
20 Correct 8 ms 468 KB correct
21 Correct 8 ms 340 KB correct
22 Correct 5 ms 340 KB correct
23 Correct 6 ms 344 KB correct
24 Correct 4 ms 340 KB correct
25 Correct 1 ms 340 KB correct
26 Correct 4 ms 340 KB correct
27 Correct 5 ms 340 KB correct
28 Correct 2 ms 340 KB correct
29 Correct 1 ms 340 KB correct
30 Correct 7 ms 468 KB correct
31 Correct 7 ms 340 KB correct
32 Correct 8 ms 432 KB correct
33 Correct 7 ms 428 KB correct
34 Incorrect 192 ms 4028 KB WA in grader: NO
35 Halted 0 ms 0 KB -