답안 #54185 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54185	2018-07-02T16:43:50 Z	radoslav11	Simurgh (IOI17_simurgh)	C++14	100 / 100	219 ms	61476 KB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"
//#include "Lgrader.cpp"

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int MAXM = (1 << 18);

struct dsu
{
	int par[MAXN], sz[MAXN];

	void init(int n) 
	{  
		for(int i = 0; i <= n; i++) 
			par[i] = i, sz[i] = 1;
	}

	int root(int x) { return par[x] == x ? x : par[x] = root(par[x]); }

	bool connected(int x, int y) { return root(x) == root(y); }

	void unite(int u, int v)
	{
		u = root(u);
		v = root(v);

		if(u == v) return;
		if(sz[u] < sz[v]) swap(u, v);

		par[v] = u;
		sz[u] += sz[v];
	}
} d;

int m, n;
pair<int, int> ed[MAXM];
vector<pair<int, int> > adj[MAXN];
int dfs_time, low[MAXN], disc[MAXN];
int low_edge[MAXN], ver[MAXN];
int E[MAXN];

int par[MAXN], pe[MAXN];
vector<int> li[MAXM];
vector<int> le, Tr;

bool cmp(int i, int j) { return min(low[ed[i].first], low[ed[i].second]) < min(low[ed[j].first], low[ed[j].second]); }

void tarjan(int u, int pr)
{
	low[u] = disc[u] = ++dfs_time;
	ver[dfs_time] = u;
	low_edge[u] = -1;

	for(auto e: adj[u])
		if(e.first != pr)
		{
			int v = e.first;
			if(!disc[v])
			{
				par[v] = u;
				pe[v] = e.second;
				tarjan(v, u);

				if(chkmin(low[u], low[v])) 
					low_edge[u] = low_edge[v];

				if(disc[u] < low[v])
					E[e.second] = 1;
			}
			else if(chkmin(low[u], disc[v]))
				low_edge[u] = e.second;
		}

	if(low_edge[u] != -1)
		le.push_back(low_edge[u]);

	if(u != pr) Tr.push_back(pe[u]);
}

int R[MAXM];
int initial;

int diff(int rem, int add)
{
	vector<int> tmp;
	for(int e: Tr)
		if(e == rem) tmp.push_back(add);
		else tmp.push_back(e);

	return count_common_roads(tmp) - initial;
}

int cnt_good(vector<int> L)
{
	d.init(::n);
	vector<int> tmp = L;
	for(int i: L)
		d.unite(ed[i].first, ed[i].second);

	int to_rem = 0;
	for(int i: Tr)
		if(!d.connected(ed[i].first, ed[i].second))
			to_rem += E[i], d.unite(ed[i].first, ed[i].second), tmp.push_back(i);

	return count_common_roads(tmp) - to_rem;
}

void rec(vector<int> &l, int sum)
{
	if(sum == 0) 
		return;

	if(l.size() == 1)
	{
		E[l.back()] = 1;
		return;
	}

	vector<int> m1, m2;
	for(int i = 0; i < (int)l.size() / 2; i++) m1.push_back(l[i]);
	for(int i = l.size() / 2; i < (int)l.size(); i++) m2.push_back(l[i]);

	int c1 = cnt_good(m1), c2 = sum - c1;
	rec(m1, c1);
	rec(m2, c2);
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) 
{
	::n = n;
	::m = u.size();
	for(int i = 0; i < ::m; i++)
	{
		ed[i] = {u[i], v[i]};
		adj[u[i]].push_back({v[i], i});
		adj[v[i]].push_back({u[i], i});
		E[i] = -1;
	}	

	tarjan(0, 0);

	sort(le.begin(), le.end());
	le.erase(unique(le.begin(), le.end()), le.end());
	sort(le.begin(), le.end(), cmp);

	initial = count_common_roads(Tr);

	for(int i: le)
	{
		int from = ed[i].first, to = ed[i].second;
		if(disc[from] > disc[to]) swap(from, to);

		while(to != from)
		{
			li[i].push_back(pe[to]);
			to = par[to];
		}

		int has = -1;
		for(int e: li[i])
			if(E[e] != -1)
				has = e;

		if(has != -1)
		{
			int df = diff(has, i);
			if(df == 0) E[i] = E[has];
			else E[i] = E[has] ^ 1;

			for(int e: li[i])
				if(E[e] == -1)
				{
					int df = diff(e, i);
					if(df == 0) E[e] = E[i];
					else E[e] = E[i] ^ 1;
				}
		}
		else
		{
			bool fl = 0;
			for(int e: li[i])
			{
				R[e] = diff(e, i);
				if(R[e]) fl = 1;
			}	

			if(!fl)
			{
				E[i] = 0;
				for(int e: li[i])
					E[e] = 0;
			}
			else
			{
				for(int e: li[i])
					if(R[e])
					{
						if(R[e] == 1) E[i] = 1;
						else E[i] = 0;
						break;
					}
				
				for(int e: li[i])
					if(E[e] == -1)
					{
						int df = R[e];
						if(df == 0) E[e] = E[i];
						else E[e] = E[i] ^ 1;
					}
			}
		}
	}

	for(int i = 0; i < n; i++)
	{
		int cnt = 0;
		vector<int> candidates;

		for(auto e: adj[i])
			if(E[e.second] == -1)
				candidates.push_back(e.second);
	
		cnt = cnt_good(candidates);
		rec(candidates, cnt);
	}

	vector<int> result;
	for(int i = 0; i < ::m; i++)
		if(E[i] == 1) 
			result.push_back(i);

	if(result.size() != ::n - 1) assert(false);

	return result;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:235:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(result.size() != ::n - 1) assert(false);
     ~~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	31096 KB	correct
2	Correct	29 ms	31204 KB	correct
3	Correct	28 ms	31280 KB	correct
4	Correct	29 ms	31424 KB	correct
5	Correct	28 ms	31424 KB	correct
6	Correct	29 ms	31424 KB	correct
7	Correct	29 ms	31424 KB	correct
8	Correct	29 ms	31424 KB	correct
9	Correct	28 ms	31424 KB	correct
10	Correct	27 ms	31540 KB	correct
11	Correct	28 ms	31540 KB	correct
12	Correct	28 ms	31540 KB	correct
13	Correct	29 ms	31540 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	31096 KB	correct
2	Correct	29 ms	31204 KB	correct
3	Correct	28 ms	31280 KB	correct
4	Correct	29 ms	31424 KB	correct
5	Correct	28 ms	31424 KB	correct
6	Correct	29 ms	31424 KB	correct
7	Correct	29 ms	31424 KB	correct
8	Correct	29 ms	31424 KB	correct
9	Correct	28 ms	31424 KB	correct
10	Correct	27 ms	31540 KB	correct
11	Correct	28 ms	31540 KB	correct
12	Correct	28 ms	31540 KB	correct
13	Correct	29 ms	31540 KB	correct
14	Correct	30 ms	31540 KB	correct
15	Correct	30 ms	31540 KB	correct
16	Correct	29 ms	31540 KB	correct
17	Correct	29 ms	31624 KB	correct
18	Correct	30 ms	31624 KB	correct
19	Correct	30 ms	31688 KB	correct
20	Correct	29 ms	31688 KB	correct
21	Correct	35 ms	31688 KB	correct
22	Correct	29 ms	31688 KB	correct
23	Correct	31 ms	31688 KB	correct
24	Correct	32 ms	31696 KB	correct
25	Correct	28 ms	31696 KB	correct
26	Correct	28 ms	31696 KB	correct
27	Correct	30 ms	31696 KB	correct
28	Correct	28 ms	31696 KB	correct
29	Correct	27 ms	31696 KB	correct
30	Correct	29 ms	31696 KB	correct
31	Correct	34 ms	31696 KB	correct
32	Correct	37 ms	31724 KB	correct
33	Correct	29 ms	31808 KB	correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	31096 KB	correct
2	Correct	29 ms	31204 KB	correct
3	Correct	28 ms	31280 KB	correct
4	Correct	29 ms	31424 KB	correct
5	Correct	28 ms	31424 KB	correct
6	Correct	29 ms	31424 KB	correct
7	Correct	29 ms	31424 KB	correct
8	Correct	29 ms	31424 KB	correct
9	Correct	28 ms	31424 KB	correct
10	Correct	27 ms	31540 KB	correct
11	Correct	28 ms	31540 KB	correct
12	Correct	28 ms	31540 KB	correct
13	Correct	29 ms	31540 KB	correct
14	Correct	30 ms	31540 KB	correct
15	Correct	30 ms	31540 KB	correct
16	Correct	29 ms	31540 KB	correct
17	Correct	29 ms	31624 KB	correct
18	Correct	30 ms	31624 KB	correct
19	Correct	30 ms	31688 KB	correct
20	Correct	29 ms	31688 KB	correct
21	Correct	35 ms	31688 KB	correct
22	Correct	29 ms	31688 KB	correct
23	Correct	31 ms	31688 KB	correct
24	Correct	32 ms	31696 KB	correct
25	Correct	28 ms	31696 KB	correct
26	Correct	28 ms	31696 KB	correct
27	Correct	30 ms	31696 KB	correct
28	Correct	28 ms	31696 KB	correct
29	Correct	27 ms	31696 KB	correct
30	Correct	29 ms	31696 KB	correct
31	Correct	34 ms	31696 KB	correct
32	Correct	37 ms	31724 KB	correct
33	Correct	29 ms	31808 KB	correct
34	Correct	62 ms	33268 KB	correct
35	Correct	60 ms	33468 KB	correct
36	Correct	57 ms	33468 KB	correct
37	Correct	36 ms	33468 KB	correct
38	Correct	73 ms	33828 KB	correct
39	Correct	58 ms	33900 KB	correct
40	Correct	69 ms	33900 KB	correct
41	Correct	63 ms	34324 KB	correct
42	Correct	81 ms	34536 KB	correct
43	Correct	45 ms	34536 KB	correct
44	Correct	42 ms	34536 KB	correct
45	Correct	47 ms	34536 KB	correct
46	Correct	54 ms	34536 KB	correct
47	Correct	36 ms	34536 KB	correct
48	Correct	31 ms	34536 KB	correct
49	Correct	36 ms	34536 KB	correct
50	Correct	40 ms	34536 KB	correct
51	Correct	44 ms	34536 KB	correct
52	Correct	44 ms	34536 KB	correct
53	Correct	41 ms	34536 KB	correct
54	Correct	59 ms	34912 KB	correct
55	Correct	45 ms	34912 KB	correct
56	Correct	46 ms	35040 KB	correct
57	Correct	43 ms	35040 KB	correct

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	35040 KB	correct
2	Correct	29 ms	35040 KB	correct
3	Correct	148 ms	38316 KB	correct
4	Correct	196 ms	41004 KB	correct
5	Correct	190 ms	41932 KB	correct
6	Correct	198 ms	42984 KB	correct
7	Correct	156 ms	43664 KB	correct
8	Correct	173 ms	44588 KB	correct
9	Correct	216 ms	45532 KB	correct
10	Correct	219 ms	46568 KB	correct
11	Correct	207 ms	47504 KB	correct
12	Correct	198 ms	48316 KB	correct
13	Correct	31 ms	48316 KB	correct
14	Correct	176 ms	49376 KB	correct
15	Correct	215 ms	50432 KB	correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	31096 KB	correct
2	Correct	29 ms	31204 KB	correct
3	Correct	28 ms	31280 KB	correct
4	Correct	29 ms	31424 KB	correct
5	Correct	28 ms	31424 KB	correct
6	Correct	29 ms	31424 KB	correct
7	Correct	29 ms	31424 KB	correct
8	Correct	29 ms	31424 KB	correct
9	Correct	28 ms	31424 KB	correct
10	Correct	27 ms	31540 KB	correct
11	Correct	28 ms	31540 KB	correct
12	Correct	28 ms	31540 KB	correct
13	Correct	29 ms	31540 KB	correct
14	Correct	30 ms	31540 KB	correct
15	Correct	30 ms	31540 KB	correct
16	Correct	29 ms	31540 KB	correct
17	Correct	29 ms	31624 KB	correct
18	Correct	30 ms	31624 KB	correct
19	Correct	30 ms	31688 KB	correct
20	Correct	29 ms	31688 KB	correct
21	Correct	35 ms	31688 KB	correct
22	Correct	29 ms	31688 KB	correct
23	Correct	31 ms	31688 KB	correct
24	Correct	32 ms	31696 KB	correct
25	Correct	28 ms	31696 KB	correct
26	Correct	28 ms	31696 KB	correct
27	Correct	30 ms	31696 KB	correct
28	Correct	28 ms	31696 KB	correct
29	Correct	27 ms	31696 KB	correct
30	Correct	29 ms	31696 KB	correct
31	Correct	34 ms	31696 KB	correct
32	Correct	37 ms	31724 KB	correct
33	Correct	29 ms	31808 KB	correct
34	Correct	62 ms	33268 KB	correct
35	Correct	60 ms	33468 KB	correct
36	Correct	57 ms	33468 KB	correct
37	Correct	36 ms	33468 KB	correct
38	Correct	73 ms	33828 KB	correct
39	Correct	58 ms	33900 KB	correct
40	Correct	69 ms	33900 KB	correct
41	Correct	63 ms	34324 KB	correct
42	Correct	81 ms	34536 KB	correct
43	Correct	45 ms	34536 KB	correct
44	Correct	42 ms	34536 KB	correct
45	Correct	47 ms	34536 KB	correct
46	Correct	54 ms	34536 KB	correct
47	Correct	36 ms	34536 KB	correct
48	Correct	31 ms	34536 KB	correct
49	Correct	36 ms	34536 KB	correct
50	Correct	40 ms	34536 KB	correct
51	Correct	44 ms	34536 KB	correct
52	Correct	44 ms	34536 KB	correct
53	Correct	41 ms	34536 KB	correct
54	Correct	59 ms	34912 KB	correct
55	Correct	45 ms	34912 KB	correct
56	Correct	46 ms	35040 KB	correct
57	Correct	43 ms	35040 KB	correct
58	Correct	30 ms	35040 KB	correct
59	Correct	29 ms	35040 KB	correct
60	Correct	148 ms	38316 KB	correct
61	Correct	196 ms	41004 KB	correct
62	Correct	190 ms	41932 KB	correct
63	Correct	198 ms	42984 KB	correct
64	Correct	156 ms	43664 KB	correct
65	Correct	173 ms	44588 KB	correct
66	Correct	216 ms	45532 KB	correct
67	Correct	219 ms	46568 KB	correct
68	Correct	207 ms	47504 KB	correct
69	Correct	198 ms	48316 KB	correct
70	Correct	31 ms	48316 KB	correct
71	Correct	176 ms	49376 KB	correct
72	Correct	215 ms	50432 KB	correct
73	Correct	31 ms	50432 KB	correct
74	Correct	206 ms	51300 KB	correct
75	Correct	190 ms	51912 KB	correct
76	Correct	107 ms	51912 KB	correct
77	Correct	192 ms	53508 KB	correct
78	Correct	195 ms	54176 KB	correct
79	Correct	209 ms	55112 KB	correct
80	Correct	188 ms	56024 KB	correct
81	Correct	135 ms	56168 KB	correct
82	Correct	187 ms	57568 KB	correct
83	Correct	170 ms	57568 KB	correct
84	Correct	95 ms	57568 KB	correct
85	Correct	92 ms	57568 KB	correct
86	Correct	80 ms	57568 KB	correct
87	Correct	86 ms	57568 KB	correct
88	Correct	67 ms	57568 KB	correct
89	Correct	73 ms	57568 KB	correct
90	Correct	65 ms	57568 KB	correct
91	Correct	46 ms	57568 KB	correct
92	Correct	42 ms	57568 KB	correct
93	Correct	91 ms	58752 KB	correct
94	Correct	78 ms	58752 KB	correct
95	Correct	104 ms	58752 KB	correct
96	Correct	73 ms	58752 KB	correct
97	Correct	77 ms	58752 KB	correct
98	Correct	98 ms	58752 KB	correct
99	Correct	67 ms	58752 KB	correct
100	Correct	57 ms	58752 KB	correct
101	Correct	41 ms	58752 KB	correct
102	Correct	84 ms	59960 KB	correct
103	Correct	94 ms	60576 KB	correct
104	Correct	100 ms	60888 KB	correct
105	Correct	97 ms	61476 KB	correct

답안 #54185

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 21.0 / 21.0

Subtask #4 19.0 / 19.0

Subtask #5 30.0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
21.0 / 21.0

Subtask #4
19.0 / 19.0

Subtask #5
30.0 / 30.0