oj.uz

Submission #831706

# Submission time Handle Problem Language Result Execution time Memory
831706 2023-08-20T12:32:54 Z Antekb Simurgh (IOI17_simurgh) C++17
30 / 100
 90 ms 5032 KB 
#include<bits/stdc++.h>
#include "simurgh.h"
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pp pop_back
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;
using ll = long long;

void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);

const int N=505;
int r[N], vis[N], par[N], paredg[N], dep[N];
int dobry[N];
int deg[N];
vii E[N];
vii edg;
int n;
int find(int v){
	if(r[v]==v)return v;
	return r[v]=find(r[v]);
}
void Union(int u, int v){
	r[find(u)]=find(v);
}
void dfs(int v){
	vis[v]=1;
	for(auto ee:E[v]){
		int u=ee.st, e=ee.nd;
		//deb(v, u);
		if(!vis[u]){
			paredg[u]=e;
			par[u]=v;
			dep[u]=dep[v]+1;
			dfs(u);
		}
	}
}
vii drz;
int licz(vi V){
	for(int i=0; i<n; i++){
		r[i]=i;
	}
	vi V2;
	int sum=0;
	for(int i:V){
		V2.pb(i);
		Union(edg[i].st, edg[i].nd);
	}
	for(pii i:drz){
		if(find(edg[i.st].st)!=find(edg[i.st].nd)){
			sum+=i.nd;
			V2.pb(i.st);
			Union(edg[i.st].st, edg[i.st].nd);
		}
	}
	int ile=count_common_roads(V2);
	return ile-sum;
}
std::vector<int> find_roads(int _n, std::vector<int> _u, std::vector<int> _v) {
	n=_n;
	for(int i=0; i<_u.size(); i++)
	{
		E[_u[i]].eb(_v[i], i);
		E[_v[i]].eb(_u[i], i);
		edg.eb(_u[i], _v[i]);
	}
	par[0]=paredg[0]=-1;
	dfs(0);
	vi V;
	for(int i=1; i<n; i++){
		r[i]=i;
		deb(i, par[i], paredg[i], dep[i]);
		V.pb(paredg[i]);
	}
	int ile=count_common_roads(V);
	for(int v=0; v<n; v++){
		for(pii ee:E[v]){
			int u=ee.st, e=ee.nd;
			if(dep[u]>dep[v] && v!=par[u]){
				vi todo;
				while(true){
					int uu=find(u);
					if(uu==find(v)){
						break;
					}
					else{
						int e2=paredg[uu];
						for(int &i:V){
							if(i==e2)i=e;
						}
						int ile2=count_common_roads(V);
						if(ile2==ile){
							todo.pb(e2);
						}
						else if(ile2>ile){
							//kraw=e;
						}
						else{
							dobry[uu]=1;
							//kraw=e2;
						}
						r[uu]=par[uu];
						for(int &i:V){
							if(i==e)i=e2;
						}
					}
				}
				for(int uu=u; uu!=v; uu=par[uu]){
					bool czy=0;
					for(int i:todo){
						if(i==paredg[uu]){
							czy=1;
							break;
						}
					}
					if(czy)continue;
					int e2=paredg[uu];
					for(int &i:V){
						if(i==e2)i=e;
					}
					int ile2=count_common_roads(V);
					if(ile2+dobry[u]>ile){
						for(int i:todo){
							if(i==paredg[edg[i].st])dobry[edg[i].st]=1;
							else dobry[edg[i].nd]=1;
						}
					}
					for(int &i:V){
						if(i==e)i=e2;
					}
					break;
				}
			}
		}
	}
	for(int i=1; i<n; i++){
		if(find(i)==i){
			dobry[i]=1;
		}
		deb(i, find(i), paredg[i], dobry[i]);
		drz.eb(paredg[i], dobry[i]);
	}
	for(int i=0; i<n; i++){
		vis[i]=0;
		vi V2;
		for(auto e:E[i]){
			V2.pb(e.nd);
		}
		deg[i]=licz(V2);
		deb(i, deg[i]);
	}
	vi ans;
	for(int ii=1; ii<n; ii++){
		int v=-1;
		for(int i=0; i<n; i++){
			if(!vis[i] && deg[i]==1){
				v=i;
			}
		}
		vi V2;
		assert(v!=-1);
		for(auto e:E[v]){
			if(!vis[e.st])V2.pb(e.nd);
		}
		int l=0, r=V2.size()-1;
		while(l<r){
			int m=(l+r)>>1;
			vi V3=V2;
			V3.resize(m+1);
			if(licz(V3)==0)l=m+1;
			else r=m;
		}
		ans.pb(V2[l]);
		int u=edg[ans.back()].st^edg[ans.back()].nd^v;
		deg[u]--;
		deg[v]--;
		vis[v]=1;
	}
	return ans;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:70:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i=0; i<_u.size(); i++)
      |               ~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 316 KB correct
3 Correct 1 ms 320 KB correct
4 Correct 1 ms 316 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 320 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 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 212 KB correct
2 Correct 1 ms 316 KB correct
3 Correct 1 ms 320 KB correct
4 Correct 1 ms 316 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 320 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 340 KB correct
14 Correct 3 ms 328 KB correct
15 Correct 3 ms 416 KB correct
16 Correct 3 ms 340 KB correct
17 Correct 3 ms 340 KB correct
18 Correct 3 ms 340 KB correct
19 Correct 4 ms 340 KB correct
20 Correct 3 ms 340 KB correct
21 Correct 3 ms 340 KB correct
22 Correct 3 ms 340 KB correct
23 Correct 3 ms 340 KB correct
24 Correct 3 ms 320 KB correct
25 Correct 2 ms 340 KB correct
26 Correct 3 ms 340 KB correct
27 Correct 3 ms 340 KB correct
28 Correct 2 ms 340 KB correct
29 Correct 2 ms 340 KB correct
30 Correct 3 ms 340 KB correct
31 Correct 3 ms 340 KB correct
32 Correct 3 ms 316 KB correct
33 Correct 3 ms 340 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 316 KB correct
3 Correct 1 ms 320 KB correct
4 Correct 1 ms 316 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 320 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 340 KB correct
14 Correct 3 ms 328 KB correct
15 Correct 3 ms 416 KB correct
16 Correct 3 ms 340 KB correct
17 Correct 3 ms 340 KB correct
18 Correct 3 ms 340 KB correct
19 Correct 4 ms 340 KB correct
20 Correct 3 ms 340 KB correct
21 Correct 3 ms 340 KB correct
22 Correct 3 ms 340 KB correct
23 Correct 3 ms 340 KB correct
24 Correct 3 ms 320 KB correct
25 Correct 2 ms 340 KB correct
26 Correct 3 ms 340 KB correct
27 Correct 3 ms 340 KB correct
28 Correct 2 ms 340 KB correct
29 Correct 2 ms 340 KB correct
30 Correct 3 ms 340 KB correct
31 Correct 3 ms 340 KB correct
32 Correct 3 ms 316 KB correct
33 Correct 3 ms 340 KB correct
34 Incorrect 90 ms 1816 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 212 KB correct
2 Correct 1 ms 212 KB correct
3 Incorrect 60 ms 5032 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 212 KB correct
2 Correct 1 ms 316 KB correct
3 Correct 1 ms 320 KB correct
4 Correct 1 ms 316 KB correct
5 Correct 1 ms 212 KB correct
6 Correct 1 ms 320 KB correct
7 Correct 1 ms 212 KB correct
8 Correct 1 ms 212 KB correct
9 Correct 1 ms 212 KB correct
10 Correct 1 ms 340 KB correct
11 Correct 1 ms 212 KB correct
12 Correct 1 ms 212 KB correct
13 Correct 1 ms 340 KB correct
14 Correct 3 ms 328 KB correct
15 Correct 3 ms 416 KB correct
16 Correct 3 ms 340 KB correct
17 Correct 3 ms 340 KB correct
18 Correct 3 ms 340 KB correct
19 Correct 4 ms 340 KB correct
20 Correct 3 ms 340 KB correct
21 Correct 3 ms 340 KB correct
22 Correct 3 ms 340 KB correct
23 Correct 3 ms 340 KB correct
24 Correct 3 ms 320 KB correct
25 Correct 2 ms 340 KB correct
26 Correct 3 ms 340 KB correct
27 Correct 3 ms 340 KB correct
28 Correct 2 ms 340 KB correct
29 Correct 2 ms 340 KB correct
30 Correct 3 ms 340 KB correct
31 Correct 3 ms 340 KB correct
32 Correct 3 ms 316 KB correct
33 Correct 3 ms 340 KB correct
34 Incorrect 90 ms 1816 KB WA in grader: NO
35 Halted 0 ms 0 KB -