oj.uz

Submission #65192

# Submission time Handle Problem Language Result Execution time Memory
65192 2018-08-07T02:51:53 Z MatheusLealV Simurgh (IOI17_simurgh) C++17
13 / 100
 166 ms 15672 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;

pii E[N], pai[N];

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

vector<int> save;

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)
			{
				pronto = ed;

				break;
			}

			u = up;
		}

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

			path.push_back(ed);

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

			v = up;			
		}
	}

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

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

		for(auto y: path)
		{
			if(ans[y] != 0) 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];
		}
	}

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

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

			int val = checa2(y, x);

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

				ans[y] = -1;
			}

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

				ans[y] = 1;
			}
		}

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

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

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);

	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;

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

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

	return resp;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10876 KB correct
2 Correct 15 ms 10980 KB correct
3 Correct 12 ms 11032 KB correct
4 Correct 12 ms 11032 KB correct
5 Correct 13 ms 11108 KB correct
6 Correct 13 ms 11108 KB correct
7 Correct 13 ms 11108 KB correct
8 Correct 13 ms 11108 KB correct
9 Correct 12 ms 11108 KB correct
10 Correct 12 ms 11108 KB correct
11 Correct 12 ms 11200 KB correct
12 Correct 11 ms 11200 KB correct
13 Correct 11 ms 11200 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10876 KB correct
2 Correct 15 ms 10980 KB correct
3 Correct 12 ms 11032 KB correct
4 Correct 12 ms 11032 KB correct
5 Correct 13 ms 11108 KB correct
6 Correct 13 ms 11108 KB correct
7 Correct 13 ms 11108 KB correct
8 Correct 13 ms 11108 KB correct
9 Correct 12 ms 11108 KB correct
10 Correct 12 ms 11108 KB correct
11 Correct 12 ms 11200 KB correct
12 Correct 11 ms 11200 KB correct
13 Correct 11 ms 11200 KB correct
14 Correct 16 ms 11244 KB correct
15 Correct 15 ms 11244 KB correct
16 Correct 19 ms 11412 KB correct
17 Correct 14 ms 11412 KB correct
18 Correct 14 ms 11412 KB correct
19 Correct 16 ms 11412 KB correct
20 Correct 14 ms 11488 KB correct
21 Correct 16 ms 11488 KB correct
22 Incorrect 15 ms 11488 KB WA in grader: NO
23 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10876 KB correct
2 Correct 15 ms 10980 KB correct
3 Correct 12 ms 11032 KB correct
4 Correct 12 ms 11032 KB correct
5 Correct 13 ms 11108 KB correct
6 Correct 13 ms 11108 KB correct
7 Correct 13 ms 11108 KB correct
8 Correct 13 ms 11108 KB correct
9 Correct 12 ms 11108 KB correct
10 Correct 12 ms 11108 KB correct
11 Correct 12 ms 11200 KB correct
12 Correct 11 ms 11200 KB correct
13 Correct 11 ms 11200 KB correct
14 Correct 16 ms 11244 KB correct
15 Correct 15 ms 11244 KB correct
16 Correct 19 ms 11412 KB correct
17 Correct 14 ms 11412 KB correct
18 Correct 14 ms 11412 KB correct
19 Correct 16 ms 11412 KB correct
20 Correct 14 ms 11488 KB correct
21 Correct 16 ms 11488 KB correct
22 Incorrect 15 ms 11488 KB WA in grader: NO
23 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11488 KB correct
2 Correct 12 ms 11488 KB correct
3 Incorrect 166 ms 15672 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10876 KB correct
2 Correct 15 ms 10980 KB correct
3 Correct 12 ms 11032 KB correct
4 Correct 12 ms 11032 KB correct
5 Correct 13 ms 11108 KB correct
6 Correct 13 ms 11108 KB correct
7 Correct 13 ms 11108 KB correct
8 Correct 13 ms 11108 KB correct
9 Correct 12 ms 11108 KB correct
10 Correct 12 ms 11108 KB correct
11 Correct 12 ms 11200 KB correct
12 Correct 11 ms 11200 KB correct
13 Correct 11 ms 11200 KB correct
14 Correct 16 ms 11244 KB correct
15 Correct 15 ms 11244 KB correct
16 Correct 19 ms 11412 KB correct
17 Correct 14 ms 11412 KB correct
18 Correct 14 ms 11412 KB correct
19 Correct 16 ms 11412 KB correct
20 Correct 14 ms 11488 KB correct
21 Correct 16 ms 11488 KB correct
22 Incorrect 15 ms 11488 KB WA in grader: NO
23 Halted 0 ms 0 KB -