oj.uz

Submission #65191

# Submission time Handle Problem Language Result Execution time Memory
65191 2018-08-07T02:45:42 Z MatheusLealV Simurgh (IOI17_simurgh) C++17
13 / 100
 21 ms 2792 KB 
#include "simurgh.h"
#define N 520
#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(auto x: save) cout<<"ARESTA "<<x<<"\n";

	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++)
	{
		//cout<<"PORRRAA "<<i<<" "<<ans[i]<<"\n";
		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 2 ms 376 KB correct
2 Correct 2 ms 488 KB correct
3 Correct 4 ms 520 KB correct
4 Correct 2 ms 680 KB correct
5 Correct 3 ms 680 KB correct
6 Correct 3 ms 680 KB correct
7 Correct 3 ms 708 KB correct
8 Correct 3 ms 708 KB correct
9 Correct 3 ms 708 KB correct
10 Correct 2 ms 752 KB correct
11 Correct 2 ms 752 KB correct
12 Correct 3 ms 760 KB correct
13 Correct 2 ms 764 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 488 KB correct
3 Correct 4 ms 520 KB correct
4 Correct 2 ms 680 KB correct
5 Correct 3 ms 680 KB correct
6 Correct 3 ms 680 KB correct
7 Correct 3 ms 708 KB correct
8 Correct 3 ms 708 KB correct
9 Correct 3 ms 708 KB correct
10 Correct 2 ms 752 KB correct
11 Correct 2 ms 752 KB correct
12 Correct 3 ms 760 KB correct
13 Correct 2 ms 764 KB correct
14 Incorrect 3 ms 768 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 488 KB correct
3 Correct 4 ms 520 KB correct
4 Correct 2 ms 680 KB correct
5 Correct 3 ms 680 KB correct
6 Correct 3 ms 680 KB correct
7 Correct 3 ms 708 KB correct
8 Correct 3 ms 708 KB correct
9 Correct 3 ms 708 KB correct
10 Correct 2 ms 752 KB correct
11 Correct 2 ms 752 KB correct
12 Correct 3 ms 760 KB correct
13 Correct 2 ms 764 KB correct
14 Incorrect 3 ms 768 KB WA in grader: NO
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 776 KB correct
2 Correct 2 ms 780 KB correct
3 Incorrect 21 ms 2792 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 488 KB correct
3 Correct 4 ms 520 KB correct
4 Correct 2 ms 680 KB correct
5 Correct 3 ms 680 KB correct
6 Correct 3 ms 680 KB correct
7 Correct 3 ms 708 KB correct
8 Correct 3 ms 708 KB correct
9 Correct 3 ms 708 KB correct
10 Correct 2 ms 752 KB correct
11 Correct 2 ms 752 KB correct
12 Correct 3 ms 760 KB correct
13 Correct 2 ms 764 KB correct
14 Incorrect 3 ms 768 KB WA in grader: NO
15 Halted 0 ms 0 KB -