oj.uz

Submission #68688

# Submission time Handle Problem Language Result Execution time Memory
68688 2018-08-18T05:46:46 Z zscoder Simurgh (IOI17_simurgh) C++17
100 / 100
 276 ms 16592 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

struct edge
{
	int to, id;
	edge(int _to, int _id) : to(_to),id(_id){}
};

vector<edge> adj[555];
int timer;
int in[555];
int royal[555555];
int par[555];
int paredge[555];
bool vis[555];
int backedge[555];
int low[555];
vector<ii> T[555];
vector<int> S;

void prep(int u=0, int p=-1)
{
	in[u]=timer++; par[u]=p; vis[u]=1; low[u]=in[u];
	for(auto X:adj[u])
	{
		int v=X.to; int lab=X.id;
		if(v==p) continue;
		if(vis[v])
		{
			if(in[v]<low[u])
			{
				low[u]=in[v];
				backedge[u]=lab;
			}
		}
		else
		{
			S.pb(lab); paredge[v]=lab;
			//cerr<<"TREE EDGE "<<u<<' '<<v<<'\n'; 
			T[u].pb(mp(v,lab)); T[v].pb(mp(u,lab));
			prep(v,u);
			if(low[v]<low[u])
			{
				low[u]=low[v];
				backedge[u]=backedge[v];
			}
		}
	}
}

int query(int u, int v) //del edge u, add edge v
{
	vi V;
	for(int x:S)
	{
		if(x!=u) V.pb(x);
	}
	V.pb(v);
	/*
	cerr<<"QUERY\n";
	for(int v:V)
	{
		cerr<<v<<' ';
	}
	cerr<<'\n';
	*/
	return count_common_roads(V);
}
vector<ii> edges;

int ask_forest(vector<int> E)
{
	vi ex;
	for(int z:E)
	{
		ii x=edges[z];
		ex.pb(x.fi); ex.pb(x.se); 
	}
	queue<int> q;
	bitset<522> used; used.reset();
	for(int x:ex) used.set(x,1);
	for(int i=0;i<511;i++){if(used[i]) q.push(i);}
	int extra=0;
	vi vec=E;
	while(!q.empty())
	{
		int u=q.front(); q.pop();
		for(ii X:T[u])
		{
			int v=X.fi; int lab=X.se;
			if(used[v]) continue;
			extra+=royal[lab]; vec.pb(lab);
			q.push(v); used.set(v,1);
		}
	}
	return count_common_roads(vec)-extra;
}

void solve(vi V, int cur)
{
	int n=V.size();
	if(n==1)
	{
		royal[V[0]]=1; return ;
	}
	vi L,R;
	for(int i=0;i<n/2;i++) L.pb(V[i]);
	for(int i=n/2;i<n;i++) R.pb(V[i]);
	int tmp = ask_forest(L);
	if(tmp>0) solve(L,tmp);
	if(cur-tmp>0) solve(R,cur-tmp);
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) 
{
	vi ans; int m=u.size();
	for(int i=0;i<m;i++) 
	{
		edges.pb(mp(u[i],v[i]));
		adj[u[i]].pb(edge(v[i],i)); adj[v[i]].pb(edge(u[i],i));
	}
	for(int i=0;i<n;i++) backedge[i]=-1;
	prep();
	for(int i=0;i<m;i++) royal[i]=-1;
	int tree_common = count_common_roads(S);
	vi backedges;
	for(int i=0;i<n;i++)
	{
		if(backedge[i]!=-1)
		{
			int x=u[backedge[i]]; int y=v[backedge[i]];
			if(in[x]<in[y]) swap(x,y);
			//cerr<<"BACK EDGE "<<i<<' '<<x<<' '<<y<<'\n';
			//x is grandchild of y
			vi path;
			while(x!=y)
			{
				path.pb(paredge[x]); x=par[x];
			}
			int known=-1;
			for(int e:path)
			{
				if(royal[e]!=-1) 
				{
					known=e;
					break;
				}
			}
			if(known==-1) //if no known edge, do the entire cycle
			{
				vi arr(int(path.size()));
				
				int exnonzero=-1;
				for(int j=0;j<path.size();j++)
				{
					arr[j]=query(path[j],backedge[i])-tree_common;
					if(arr[j]!=0) exnonzero=j;
				}
				
				//all 0 => none of them is part of tree because it's a cycle
				if(exnonzero==-1)
				{
					for(int v:path) royal[v]=0;
					royal[backedge[i]]=0;
				}
				else
				{
					if(arr[exnonzero]==1) //meaning backedge[i] is good
					{
						royal[backedge[i]]=1;
						for(int i=0;i<path.size();i++)
						{
							if(arr[i]==1) royal[path[i]]=0;
							else royal[path[i]]=1;
						}
					}
					else
					{
						royal[backedge[i]]=0;
						for(int i=0;i<path.size();i++)
						{
							if(arr[i]==0) royal[path[i]]=0;
							else royal[path[i]]=1;
						}
					}
				}
				/*
				cerr<<"RESULT : \n";
				for(int v:path) cerr<<v<<' '<<royal[v]<<'\n';
				cerr<<backedge[i]<<' '<<royal[backedge[i]]<<'\n';
				cerr<<'\n';
				*/
			}
			else //known is a known tree edge
			{
				int v = query(known, backedge[i]) - tree_common;
				v+=royal[known]; royal[backedge[i]]=v;
				for(int e:path)
				{
					if(royal[e]==-1)
					{
						int val = tree_common-query(e,backedge[i]);
						val+=royal[backedge[i]];
						royal[e]=val;
					}
				}
				/*
				cerr<<"RESULT : \n";
				for(int v:path) cerr<<v<<' '<<royal[v]<<'\n';
				cerr<<backedge[i]<<' '<<royal[backedge[i]]<<'\n';
				cerr<<'\n';
				*/
			}
		}
	}
	for(int e:S)
	{
		if(royal[e]==-1) royal[e]=1; //because it is a bridge
	}
	//now we should have determined the affinity of all the tree edges
	//optimize this part to nlogn
	/*
	for(int i=0;i<m;i++)
	{
		if(royal[i]==-1)
		{
			int x=u[i]; int y=v[i];
			if(in[x]<in[y]) swap(x,y);
			//x is a grandchild of y
			int v = query(paredge[x], i) - tree_common;
			v+=royal[paredge[x]];
			royal[i]=v;
		}
	}
	*/
	for(int i=0;i<m;i++)
	{
		if(royal[i]==-1) royal[i]=0;
	}
	for(int i=0;i<n;i++)
	{
		vi V;
		for(edge v:adj[i])
		{
			if(v.to>i) V.pb(v.id);
		}
		if(V.empty()) continue;
		int ans = ask_forest(V);
		if(ans>0) solve(V,ans);
	}
	for(int i=0;i<m;i++)
	{
		if(royal[i]) ans.pb(i);
	}
	return ans;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:171:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<path.size();j++)
                 ~^~~~~~~~~~~~
simurgh.cpp:188:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<path.size();i++)
                   ~^~~~~~~~~~~~
simurgh.cpp:197:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<path.size();i++)
                   ~^~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 2 ms 380 KB correct
3 Correct 3 ms 596 KB correct
4 Correct 2 ms 596 KB correct
5 Correct 2 ms 596 KB correct
6 Correct 3 ms 596 KB correct
7 Correct 4 ms 596 KB correct
8 Correct 2 ms 596 KB correct
9 Correct 2 ms 604 KB correct
10 Correct 2 ms 636 KB correct
11 Correct 3 ms 636 KB correct
12 Correct 2 ms 636 KB correct
13 Correct 2 ms 636 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 2 ms 380 KB correct
3 Correct 3 ms 596 KB correct
4 Correct 2 ms 596 KB correct
5 Correct 2 ms 596 KB correct
6 Correct 3 ms 596 KB correct
7 Correct 4 ms 596 KB correct
8 Correct 2 ms 596 KB correct
9 Correct 2 ms 604 KB correct
10 Correct 2 ms 636 KB correct
11 Correct 3 ms 636 KB correct
12 Correct 2 ms 636 KB correct
13 Correct 2 ms 636 KB correct
14 Correct 5 ms 640 KB correct
15 Correct 3 ms 764 KB correct
16 Correct 4 ms 764 KB correct
17 Correct 4 ms 764 KB correct
18 Correct 4 ms 764 KB correct
19 Correct 7 ms 764 KB correct
20 Correct 4 ms 764 KB correct
21 Correct 5 ms 764 KB correct
22 Correct 3 ms 764 KB correct
23 Correct 4 ms 764 KB correct
24 Correct 5 ms 764 KB correct
25 Correct 3 ms 764 KB correct
26 Correct 4 ms 764 KB correct
27 Correct 5 ms 764 KB correct
28 Correct 3 ms 764 KB correct
29 Correct 4 ms 764 KB correct
30 Correct 4 ms 764 KB correct
31 Correct 4 ms 764 KB correct
32 Correct 4 ms 764 KB correct
33 Correct 4 ms 764 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 2 ms 380 KB correct
3 Correct 3 ms 596 KB correct
4 Correct 2 ms 596 KB correct
5 Correct 2 ms 596 KB correct
6 Correct 3 ms 596 KB correct
7 Correct 4 ms 596 KB correct
8 Correct 2 ms 596 KB correct
9 Correct 2 ms 604 KB correct
10 Correct 2 ms 636 KB correct
11 Correct 3 ms 636 KB correct
12 Correct 2 ms 636 KB correct
13 Correct 2 ms 636 KB correct
14 Correct 5 ms 640 KB correct
15 Correct 3 ms 764 KB correct
16 Correct 4 ms 764 KB correct
17 Correct 4 ms 764 KB correct
18 Correct 4 ms 764 KB correct
19 Correct 7 ms 764 KB correct
20 Correct 4 ms 764 KB correct
21 Correct 5 ms 764 KB correct
22 Correct 3 ms 764 KB correct
23 Correct 4 ms 764 KB correct
24 Correct 5 ms 764 KB correct
25 Correct 3 ms 764 KB correct
26 Correct 4 ms 764 KB correct
27 Correct 5 ms 764 KB correct
28 Correct 3 ms 764 KB correct
29 Correct 4 ms 764 KB correct
30 Correct 4 ms 764 KB correct
31 Correct 4 ms 764 KB correct
32 Correct 4 ms 764 KB correct
33 Correct 4 ms 764 KB correct
34 Correct 47 ms 1928 KB correct
35 Correct 46 ms 1928 KB correct
36 Correct 54 ms 1928 KB correct
37 Correct 17 ms 1928 KB correct
38 Correct 55 ms 1928 KB correct
39 Correct 44 ms 1928 KB correct
40 Correct 37 ms 1928 KB correct
41 Correct 47 ms 1928 KB correct
42 Correct 54 ms 1940 KB correct
43 Correct 31 ms 1940 KB correct
44 Correct 33 ms 1940 KB correct
45 Correct 26 ms 1940 KB correct
46 Correct 27 ms 1940 KB correct
47 Correct 23 ms 1940 KB correct
48 Correct 8 ms 1940 KB correct
49 Correct 14 ms 1940 KB correct
50 Correct 20 ms 1940 KB correct
51 Correct 27 ms 1940 KB correct
52 Correct 26 ms 1940 KB correct
53 Correct 25 ms 1940 KB correct
54 Correct 36 ms 1940 KB correct
55 Correct 33 ms 1940 KB correct
56 Correct 35 ms 1940 KB correct
57 Correct 28 ms 1940 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1940 KB correct
2 Correct 2 ms 1940 KB correct
3 Correct 126 ms 4740 KB correct
4 Correct 195 ms 6268 KB correct
5 Correct 226 ms 6272 KB correct
6 Correct 203 ms 6400 KB correct
7 Correct 137 ms 6400 KB correct
8 Correct 143 ms 6400 KB correct
9 Correct 232 ms 6400 KB correct
10 Correct 276 ms 6400 KB correct
11 Correct 221 ms 6400 KB correct
12 Correct 226 ms 6400 KB correct
13 Correct 2 ms 6400 KB correct
14 Correct 172 ms 6400 KB correct
15 Correct 196 ms 6400 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 2 ms 380 KB correct
3 Correct 3 ms 596 KB correct
4 Correct 2 ms 596 KB correct
5 Correct 2 ms 596 KB correct
6 Correct 3 ms 596 KB correct
7 Correct 4 ms 596 KB correct
8 Correct 2 ms 596 KB correct
9 Correct 2 ms 604 KB correct
10 Correct 2 ms 636 KB correct
11 Correct 3 ms 636 KB correct
12 Correct 2 ms 636 KB correct
13 Correct 2 ms 636 KB correct
14 Correct 5 ms 640 KB correct
15 Correct 3 ms 764 KB correct
16 Correct 4 ms 764 KB correct
17 Correct 4 ms 764 KB correct
18 Correct 4 ms 764 KB correct
19 Correct 7 ms 764 KB correct
20 Correct 4 ms 764 KB correct
21 Correct 5 ms 764 KB correct
22 Correct 3 ms 764 KB correct
23 Correct 4 ms 764 KB correct
24 Correct 5 ms 764 KB correct
25 Correct 3 ms 764 KB correct
26 Correct 4 ms 764 KB correct
27 Correct 5 ms 764 KB correct
28 Correct 3 ms 764 KB correct
29 Correct 4 ms 764 KB correct
30 Correct 4 ms 764 KB correct
31 Correct 4 ms 764 KB correct
32 Correct 4 ms 764 KB correct
33 Correct 4 ms 764 KB correct
34 Correct 47 ms 1928 KB correct
35 Correct 46 ms 1928 KB correct
36 Correct 54 ms 1928 KB correct
37 Correct 17 ms 1928 KB correct
38 Correct 55 ms 1928 KB correct
39 Correct 44 ms 1928 KB correct
40 Correct 37 ms 1928 KB correct
41 Correct 47 ms 1928 KB correct
42 Correct 54 ms 1940 KB correct
43 Correct 31 ms 1940 KB correct
44 Correct 33 ms 1940 KB correct
45 Correct 26 ms 1940 KB correct
46 Correct 27 ms 1940 KB correct
47 Correct 23 ms 1940 KB correct
48 Correct 8 ms 1940 KB correct
49 Correct 14 ms 1940 KB correct
50 Correct 20 ms 1940 KB correct
51 Correct 27 ms 1940 KB correct
52 Correct 26 ms 1940 KB correct
53 Correct 25 ms 1940 KB correct
54 Correct 36 ms 1940 KB correct
55 Correct 33 ms 1940 KB correct
56 Correct 35 ms 1940 KB correct
57 Correct 28 ms 1940 KB correct
58 Correct 2 ms 1940 KB correct
59 Correct 2 ms 1940 KB correct
60 Correct 126 ms 4740 KB correct
61 Correct 195 ms 6268 KB correct
62 Correct 226 ms 6272 KB correct
63 Correct 203 ms 6400 KB correct
64 Correct 137 ms 6400 KB correct
65 Correct 143 ms 6400 KB correct
66 Correct 232 ms 6400 KB correct
67 Correct 276 ms 6400 KB correct
68 Correct 221 ms 6400 KB correct
69 Correct 226 ms 6400 KB correct
70 Correct 2 ms 6400 KB correct
71 Correct 172 ms 6400 KB correct
72 Correct 196 ms 6400 KB correct
73 Correct 3 ms 6400 KB correct
74 Correct 202 ms 6528 KB correct
75 Correct 202 ms 7296 KB correct
76 Correct 123 ms 7296 KB correct
77 Correct 207 ms 8648 KB correct
78 Correct 216 ms 9512 KB correct
79 Correct 221 ms 10436 KB correct
80 Correct 231 ms 11136 KB correct
81 Correct 146 ms 11408 KB correct
82 Correct 240 ms 12940 KB correct
83 Correct 180 ms 12940 KB correct
84 Correct 125 ms 12940 KB correct
85 Correct 146 ms 12940 KB correct
86 Correct 132 ms 12940 KB correct
87 Correct 125 ms 12940 KB correct
88 Correct 94 ms 12940 KB correct
89 Correct 82 ms 12940 KB correct
90 Correct 117 ms 12940 KB correct
91 Correct 44 ms 12940 KB correct
92 Correct 33 ms 12940 KB correct
93 Correct 142 ms 14012 KB correct
94 Correct 101 ms 14012 KB correct
95 Correct 90 ms 14012 KB correct
96 Correct 77 ms 14012 KB correct
97 Correct 82 ms 14012 KB correct
98 Correct 86 ms 14012 KB correct
99 Correct 90 ms 14012 KB correct
100 Correct 55 ms 14012 KB correct
101 Correct 36 ms 14012 KB correct
102 Correct 138 ms 15204 KB correct
103 Correct 140 ms 15708 KB correct
104 Correct 138 ms 16124 KB correct
105 Correct 141 ms 16592 KB correct