oj.uz

Submission #65198

# Submission time Handle Problem Language Result Execution time Memory
65198 2018-08-07T03:27:48 Z MatheusLealV Simurgh (IOI17_simurgh) C++17
51 / 100
 286 ms 16504 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -