답안 #65198 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65198	2018-08-07T03:27:48 Z	MatheusLealV	Simurgh (IOI17_simurgh)	C++17	51 / 100	286 ms	16504 KB

simurgh

#include "simurgh.h"
#define N 225000
#define f first
#define ss second
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int n, m, peso[N],ok[N], st[N], nivel[N], ans[N], valor;

int ponte[N];

pii E[N], pai[N];

vector<pii> grafo[N], tree[N];

vector<int> save;

int cnt, dfsnum[N], dfslow[N], paii[N];

void dfs2(int x)
{
	dfsnum[x] = dfslow[x] = ++cnt;
 
	for(int i = 0; i< grafo[x].size(); i++)
	{
		int v = grafo[x][i].f, id = grafo[x][i].ss;
 
		if(!dfsnum[v])
		{
			paii[v] = x;
 
			dfs2(v);
 
			if(dfslow[v] > dfsnum[x]) ponte[id] = 1;
 
			dfslow[x] = min(dfslow[v], dfslow[x]);
		}
 
		else if(v != paii[x]) dfslow[x] = min(dfsnum[v], dfslow[x]);
	}
}

void dfs(int x)
{
	ok[x] = 1;

	random_shuffle(grafo[x].begin(), grafo[x].end());

	for(auto v: grafo[x])
	{
		if(ok[v.f]) continue;

		tree[x].push_back({v.f, v.ss});

		tree[v.f].push_back({x, v.ss});

		pai[v.f] = {x, v.ss};

		nivel[v.f] = nivel[x] + 1;

		save.push_back(v.ss);

		st[v.ss] = 1;

		dfs(v.f);
	}
}

int checa1(int antiga, int nova)
{	
	vector<int> aux;

	for(auto x: save)
	{
		if(x == antiga) continue;

		aux.push_back(x);
	}

	aux.push_back(nova);

	int val = count_common_roads(aux);

	if(val > valor) return 1;

	if(val < valor) return -1;

	return ans[antiga];
}

int checa2(int antiga, int nova)
{
	vector<int> aux;

	for(auto x: save)
	{
		if(x == antiga) continue;

		aux.push_back(x);
	}

	aux.push_back(nova);

	int val = count_common_roads(aux);

	if(val > valor) return 1;

	if(val < valor) return -1;

	return 0;
}

void solve(int x)
{
	int u = E[x].f, v = E[x].ss, pronto = -1;

	vector<int> path;

	while(u != v)
	{
		if(nivel[u] > nivel[v])
		{
			int up = pai[u].f, ed = pai[u].ss;

			path.push_back(ed);

			if(ans[ed] != 0 and ed != x)
			{
				pronto = ed;

				//break;
			}

			u = up;
		}

		else
		{
			int up = pai[v].f, ed = pai[v].ss;

			path.push_back(ed);

			if(ans[ed] != 0 and ed != x)
			{
				pronto = ed;
			}

			v = up;			
		}
	}

	//cout<<"CHECA XIZ "<<x<<"\n";

	if(pronto == -1 and ans[x] == 0)
	{
		vector<int> iguais;

		for(auto y: path)
		{
			//cout<<"REMOVE "<<y<<" ADD "<<x<<"\n";

			//cout<<"CHECA 2 "<<y<<"\n";

			if(ans[x] != 0 and ans[y] != 0) continue;

			if(x == y) continue;

			int val = checa2(y, x);

			if(val == 1)
			{
				ans[x] = 1;

				ans[y] = -1;
			}

			else if(val == -1)
			{
				ans[x] = -1;

				ans[y] = 1;
			}

			else iguais.push_back(y);
		}

		if(ans[x] == 0)
		{
			ans[x] = -1;

			for(auto y: path) ans[y] = -1;
		}

		for(auto y: iguais) ans[y] = ans[x];
	}

	if(ans[x] == 0 and pronto != -1) ans[x] = checa1(pronto,x);

	for(auto y: path)
	{
		if(ans[y] != 0 or x== y) continue;

		//cout<<"CHECA 1 "<<y<<"\n";

		int val = checa1(y, x);

		if(val > 0) ans[y] = -1;

		else if(val < 0) ans[y] = 1;

		else ans[y] = ans[x];
	}
}

vector<int> find_roads(int ni, vector<int> u, vector<int> v)
{
	n = ni, m = (int)u.size();

	for(int i = 0; i < m; i++)
	{
		E[i] = {u[i], v[i]};

		grafo[u[i]].push_back({v[i], i});

		grafo[v[i]].push_back({u[i], i});
	}

	pai[0] = {0, 0};

	dfs(0);

	dfs2(0);

	valor = count_common_roads(save);

	if(valor == n - 1) return save;

	for(int i = 0; i < m; i++)
	{
		if(st[i]) continue;

		//cout<<"OK "<<i<<"\n";

		solve(i);

	}

	vector<int> resp;

	set<int> ss;

	for(int i = 0; i < m; i++)
	{
		if(ans[i] >= 0) resp.push_back(i);
	}

	resp.resize(n - 1);

	sort(resp.begin(), resp.end());

	return resp;
}

Compilation message

simurgh.cpp: In function 'void dfs2(int)':
simurgh.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i< grafo[x].size(); i++)
                 ~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	10872 KB	correct
2	Correct	12 ms	10980 KB	correct
3	Correct	15 ms	11016 KB	correct
4	Correct	14 ms	11064 KB	correct
5	Correct	13 ms	11064 KB	correct
6	Correct	13 ms	11064 KB	correct
7	Correct	12 ms	11064 KB	correct
8	Correct	11 ms	11116 KB	correct
9	Correct	11 ms	11116 KB	correct
10	Correct	12 ms	11116 KB	correct
11	Correct	14 ms	11192 KB	correct
12	Correct	12 ms	11316 KB	correct
13	Correct	14 ms	11316 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	10872 KB	correct
2	Correct	12 ms	10980 KB	correct
3	Correct	15 ms	11016 KB	correct
4	Correct	14 ms	11064 KB	correct
5	Correct	13 ms	11064 KB	correct
6	Correct	13 ms	11064 KB	correct
7	Correct	12 ms	11064 KB	correct
8	Correct	11 ms	11116 KB	correct
9	Correct	11 ms	11116 KB	correct
10	Correct	12 ms	11116 KB	correct
11	Correct	14 ms	11192 KB	correct
12	Correct	12 ms	11316 KB	correct
13	Correct	14 ms	11316 KB	correct
14	Correct	19 ms	11316 KB	correct
15	Correct	15 ms	11316 KB	correct
16	Correct	17 ms	11316 KB	correct
17	Correct	18 ms	11316 KB	correct
18	Correct	15 ms	11316 KB	correct
19	Correct	16 ms	11316 KB	correct
20	Correct	16 ms	11372 KB	correct
21	Correct	40 ms	11372 KB	correct
22	Correct	15 ms	11372 KB	correct
23	Correct	16 ms	11372 KB	correct
24	Correct	13 ms	11372 KB	correct
25	Correct	12 ms	11372 KB	correct
26	Correct	15 ms	11372 KB	correct
27	Correct	16 ms	11372 KB	correct
28	Correct	13 ms	11372 KB	correct
29	Correct	12 ms	11372 KB	correct
30	Correct	16 ms	11372 KB	correct
31	Correct	14 ms	11372 KB	correct
32	Correct	14 ms	11372 KB	correct
33	Correct	14 ms	11372 KB	correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	10872 KB	correct
2	Correct	12 ms	10980 KB	correct
3	Correct	15 ms	11016 KB	correct
4	Correct	14 ms	11064 KB	correct
5	Correct	13 ms	11064 KB	correct
6	Correct	13 ms	11064 KB	correct
7	Correct	12 ms	11064 KB	correct
8	Correct	11 ms	11116 KB	correct
9	Correct	11 ms	11116 KB	correct
10	Correct	12 ms	11116 KB	correct
11	Correct	14 ms	11192 KB	correct
12	Correct	12 ms	11316 KB	correct
13	Correct	14 ms	11316 KB	correct
14	Correct	19 ms	11316 KB	correct
15	Correct	15 ms	11316 KB	correct
16	Correct	17 ms	11316 KB	correct
17	Correct	18 ms	11316 KB	correct
18	Correct	15 ms	11316 KB	correct
19	Correct	16 ms	11316 KB	correct
20	Correct	16 ms	11372 KB	correct
21	Correct	40 ms	11372 KB	correct
22	Correct	15 ms	11372 KB	correct
23	Correct	16 ms	11372 KB	correct
24	Correct	13 ms	11372 KB	correct
25	Correct	12 ms	11372 KB	correct
26	Correct	15 ms	11372 KB	correct
27	Correct	16 ms	11372 KB	correct
28	Correct	13 ms	11372 KB	correct
29	Correct	12 ms	11372 KB	correct
30	Correct	16 ms	11372 KB	correct
31	Correct	14 ms	11372 KB	correct
32	Correct	14 ms	11372 KB	correct
33	Correct	14 ms	11372 KB	correct
34	Correct	269 ms	12672 KB	correct
35	Correct	215 ms	12672 KB	correct
36	Correct	202 ms	12672 KB	correct
37	Correct	23 ms	12672 KB	correct
38	Correct	252 ms	12672 KB	correct
39	Correct	186 ms	12672 KB	correct
40	Correct	136 ms	12672 KB	correct
41	Correct	230 ms	12672 KB	correct
42	Correct	286 ms	12692 KB	correct
43	Correct	123 ms	12692 KB	correct
44	Correct	93 ms	12692 KB	correct
45	Correct	113 ms	12692 KB	correct
46	Correct	86 ms	12692 KB	correct
47	Correct	55 ms	12692 KB	correct
48	Correct	18 ms	12692 KB	correct
49	Correct	23 ms	12692 KB	correct
50	Correct	43 ms	12692 KB	correct
51	Correct	123 ms	12692 KB	correct
52	Correct	119 ms	12692 KB	correct
53	Correct	99 ms	12692 KB	correct
54	Correct	141 ms	12740 KB	correct
55	Correct	145 ms	12740 KB	correct
56	Correct	168 ms	12740 KB	correct
57	Correct	145 ms	12816 KB	correct

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	12816 KB	correct
2	Correct	13 ms	12816 KB	correct
3	Incorrect	241 ms	16504 KB	WA in grader: NO
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	10872 KB	correct
2	Correct	12 ms	10980 KB	correct
3	Correct	15 ms	11016 KB	correct
4	Correct	14 ms	11064 KB	correct
5	Correct	13 ms	11064 KB	correct
6	Correct	13 ms	11064 KB	correct
7	Correct	12 ms	11064 KB	correct
8	Correct	11 ms	11116 KB	correct
9	Correct	11 ms	11116 KB	correct
10	Correct	12 ms	11116 KB	correct
11	Correct	14 ms	11192 KB	correct
12	Correct	12 ms	11316 KB	correct
13	Correct	14 ms	11316 KB	correct
14	Correct	19 ms	11316 KB	correct
15	Correct	15 ms	11316 KB	correct
16	Correct	17 ms	11316 KB	correct
17	Correct	18 ms	11316 KB	correct
18	Correct	15 ms	11316 KB	correct
19	Correct	16 ms	11316 KB	correct
20	Correct	16 ms	11372 KB	correct
21	Correct	40 ms	11372 KB	correct
22	Correct	15 ms	11372 KB	correct
23	Correct	16 ms	11372 KB	correct
24	Correct	13 ms	11372 KB	correct
25	Correct	12 ms	11372 KB	correct
26	Correct	15 ms	11372 KB	correct
27	Correct	16 ms	11372 KB	correct
28	Correct	13 ms	11372 KB	correct
29	Correct	12 ms	11372 KB	correct
30	Correct	16 ms	11372 KB	correct
31	Correct	14 ms	11372 KB	correct
32	Correct	14 ms	11372 KB	correct
33	Correct	14 ms	11372 KB	correct
34	Correct	269 ms	12672 KB	correct
35	Correct	215 ms	12672 KB	correct
36	Correct	202 ms	12672 KB	correct
37	Correct	23 ms	12672 KB	correct
38	Correct	252 ms	12672 KB	correct
39	Correct	186 ms	12672 KB	correct
40	Correct	136 ms	12672 KB	correct
41	Correct	230 ms	12672 KB	correct
42	Correct	286 ms	12692 KB	correct
43	Correct	123 ms	12692 KB	correct
44	Correct	93 ms	12692 KB	correct
45	Correct	113 ms	12692 KB	correct
46	Correct	86 ms	12692 KB	correct
47	Correct	55 ms	12692 KB	correct
48	Correct	18 ms	12692 KB	correct
49	Correct	23 ms	12692 KB	correct
50	Correct	43 ms	12692 KB	correct
51	Correct	123 ms	12692 KB	correct
52	Correct	119 ms	12692 KB	correct
53	Correct	99 ms	12692 KB	correct
54	Correct	141 ms	12740 KB	correct
55	Correct	145 ms	12740 KB	correct
56	Correct	168 ms	12740 KB	correct
57	Correct	145 ms	12816 KB	correct
58	Correct	15 ms	12816 KB	correct
59	Correct	13 ms	12816 KB	correct
60	Incorrect	241 ms	16504 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #65198

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