oj.uz

Submission #65197

# Submission time Handle Problem Language Result Execution time Memory
65197 2018-08-07T03:21:12 Z MatheusLealV Simurgh (IOI17_simurgh) C++17
0 / 100
 161 ms 15420 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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11004 KB correct
2 Correct 11 ms 11004 KB correct
3 Correct 11 ms 11060 KB correct
4 Incorrect 14 ms 11208 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11004 KB correct
2 Correct 11 ms 11004 KB correct
3 Correct 11 ms 11060 KB correct
4 Incorrect 14 ms 11208 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11004 KB correct
2 Correct 11 ms 11004 KB correct
3 Correct 11 ms 11060 KB correct
4 Incorrect 14 ms 11208 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11208 KB correct
2 Correct 13 ms 11208 KB correct
3 Incorrect 161 ms 15420 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11004 KB correct
2 Correct 11 ms 11004 KB correct
3 Correct 11 ms 11060 KB correct
4 Incorrect 14 ms 11208 KB WA in grader: NO
5 Halted 0 ms 0 KB -