답안 #68686 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68686	2018-08-18T05:20:22 Z	zscoder	Simurgh (IOI17_simurgh)	C++17	51 / 100	165 ms	6892 KB

simurgh

#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<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';
			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);
}

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++) 
	{
		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
	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]) 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:124:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<path.size();j++)
                 ~^~~~~~~~~~~~
simurgh.cpp:141:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<path.size();i++)
                   ~^~~~~~~~~~~~
simurgh.cpp:150: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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	correct
2	Correct	2 ms	376 KB	correct
3	Correct	2 ms	432 KB	correct
4	Correct	3 ms	508 KB	correct
5	Correct	2 ms	544 KB	correct
6	Correct	2 ms	544 KB	correct
7	Correct	3 ms	544 KB	correct
8	Correct	2 ms	544 KB	correct
9	Correct	2 ms	544 KB	correct
10	Correct	2 ms	544 KB	correct
11	Correct	3 ms	544 KB	correct
12	Correct	3 ms	544 KB	correct
13	Correct	2 ms	548 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	correct
2	Correct	2 ms	376 KB	correct
3	Correct	2 ms	432 KB	correct
4	Correct	3 ms	508 KB	correct
5	Correct	2 ms	544 KB	correct
6	Correct	2 ms	544 KB	correct
7	Correct	3 ms	544 KB	correct
8	Correct	2 ms	544 KB	correct
9	Correct	2 ms	544 KB	correct
10	Correct	2 ms	544 KB	correct
11	Correct	3 ms	544 KB	correct
12	Correct	3 ms	544 KB	correct
13	Correct	2 ms	548 KB	correct
14	Correct	4 ms	548 KB	correct
15	Correct	7 ms	548 KB	correct
16	Correct	5 ms	584 KB	correct
17	Correct	5 ms	640 KB	correct
18	Correct	3 ms	640 KB	correct
19	Correct	6 ms	640 KB	correct
20	Correct	6 ms	644 KB	correct
21	Correct	4 ms	832 KB	correct
22	Correct	4 ms	832 KB	correct
23	Correct	4 ms	832 KB	correct
24	Correct	4 ms	832 KB	correct
25	Correct	3 ms	832 KB	correct
26	Correct	4 ms	832 KB	correct
27	Correct	4 ms	832 KB	correct
28	Correct	4 ms	832 KB	correct
29	Correct	3 ms	832 KB	correct
30	Correct	3 ms	836 KB	correct
31	Correct	4 ms	840 KB	correct
32	Correct	4 ms	844 KB	correct
33	Correct	5 ms	856 KB	correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	correct
2	Correct	2 ms	376 KB	correct
3	Correct	2 ms	432 KB	correct
4	Correct	3 ms	508 KB	correct
5	Correct	2 ms	544 KB	correct
6	Correct	2 ms	544 KB	correct
7	Correct	3 ms	544 KB	correct
8	Correct	2 ms	544 KB	correct
9	Correct	2 ms	544 KB	correct
10	Correct	2 ms	544 KB	correct
11	Correct	3 ms	544 KB	correct
12	Correct	3 ms	544 KB	correct
13	Correct	2 ms	548 KB	correct
14	Correct	4 ms	548 KB	correct
15	Correct	7 ms	548 KB	correct
16	Correct	5 ms	584 KB	correct
17	Correct	5 ms	640 KB	correct
18	Correct	3 ms	640 KB	correct
19	Correct	6 ms	640 KB	correct
20	Correct	6 ms	644 KB	correct
21	Correct	4 ms	832 KB	correct
22	Correct	4 ms	832 KB	correct
23	Correct	4 ms	832 KB	correct
24	Correct	4 ms	832 KB	correct
25	Correct	3 ms	832 KB	correct
26	Correct	4 ms	832 KB	correct
27	Correct	4 ms	832 KB	correct
28	Correct	4 ms	832 KB	correct
29	Correct	3 ms	832 KB	correct
30	Correct	3 ms	836 KB	correct
31	Correct	4 ms	840 KB	correct
32	Correct	4 ms	844 KB	correct
33	Correct	5 ms	856 KB	correct
34	Correct	165 ms	2136 KB	correct
35	Correct	161 ms	2240 KB	correct
36	Correct	111 ms	2276 KB	correct
37	Correct	11 ms	2276 KB	correct
38	Correct	152 ms	2696 KB	correct
39	Correct	134 ms	2812 KB	correct
40	Correct	117 ms	2812 KB	correct
41	Correct	156 ms	3204 KB	correct
42	Correct	147 ms	3408 KB	correct
43	Correct	84 ms	3408 KB	correct
44	Correct	64 ms	3408 KB	correct
45	Correct	80 ms	3408 KB	correct
46	Correct	54 ms	3408 KB	correct
47	Correct	28 ms	3408 KB	correct
48	Correct	5 ms	3408 KB	correct
49	Correct	14 ms	3408 KB	correct
50	Correct	28 ms	3408 KB	correct
51	Correct	78 ms	3440 KB	correct
52	Correct	59 ms	3496 KB	correct
53	Correct	59 ms	3500 KB	correct
54	Correct	87 ms	3832 KB	correct
55	Correct	76 ms	3832 KB	correct
56	Correct	82 ms	3988 KB	correct
57	Correct	74 ms	4036 KB	correct

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	correct
2	Correct	2 ms	376 KB	correct
3	Correct	2 ms	432 KB	correct
4	Correct	3 ms	508 KB	correct
5	Correct	2 ms	544 KB	correct
6	Correct	2 ms	544 KB	correct
7	Correct	3 ms	544 KB	correct
8	Correct	2 ms	544 KB	correct
9	Correct	2 ms	544 KB	correct
10	Correct	2 ms	544 KB	correct
11	Correct	3 ms	544 KB	correct
12	Correct	3 ms	544 KB	correct
13	Correct	2 ms	548 KB	correct
14	Correct	4 ms	548 KB	correct
15	Correct	7 ms	548 KB	correct
16	Correct	5 ms	584 KB	correct
17	Correct	5 ms	640 KB	correct
18	Correct	3 ms	640 KB	correct
19	Correct	6 ms	640 KB	correct
20	Correct	6 ms	644 KB	correct
21	Correct	4 ms	832 KB	correct
22	Correct	4 ms	832 KB	correct
23	Correct	4 ms	832 KB	correct
24	Correct	4 ms	832 KB	correct
25	Correct	3 ms	832 KB	correct
26	Correct	4 ms	832 KB	correct
27	Correct	4 ms	832 KB	correct
28	Correct	4 ms	832 KB	correct
29	Correct	3 ms	832 KB	correct
30	Correct	3 ms	836 KB	correct
31	Correct	4 ms	840 KB	correct
32	Correct	4 ms	844 KB	correct
33	Correct	5 ms	856 KB	correct
34	Correct	165 ms	2136 KB	correct
35	Correct	161 ms	2240 KB	correct
36	Correct	111 ms	2276 KB	correct
37	Correct	11 ms	2276 KB	correct
38	Correct	152 ms	2696 KB	correct
39	Correct	134 ms	2812 KB	correct
40	Correct	117 ms	2812 KB	correct
41	Correct	156 ms	3204 KB	correct
42	Correct	147 ms	3408 KB	correct
43	Correct	84 ms	3408 KB	correct
44	Correct	64 ms	3408 KB	correct
45	Correct	80 ms	3408 KB	correct
46	Correct	54 ms	3408 KB	correct
47	Correct	28 ms	3408 KB	correct
48	Correct	5 ms	3408 KB	correct
49	Correct	14 ms	3408 KB	correct
50	Correct	28 ms	3408 KB	correct
51	Correct	78 ms	3440 KB	correct
52	Correct	59 ms	3496 KB	correct
53	Correct	59 ms	3500 KB	correct
54	Correct	87 ms	3832 KB	correct
55	Correct	76 ms	3832 KB	correct
56	Correct	82 ms	3988 KB	correct
57	Correct	74 ms	4036 KB	correct
58	Correct	2 ms	4036 KB	correct
59	Correct	2 ms	4036 KB	correct
60	Incorrect	142 ms	6892 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #68686

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0