Submission #977708

#	Time	Username	Problem	Language	Result	Execution time	Memory
977708		JwFXoiz	Simurgh (IOI17_simurgh)	C++14	0 / 100	3020 ms	504 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

const int MXN = 5e2 + 5;

int N;
vector<array<int, 2>> adj[MXN];
vector<int> res;
vector<int> col, used, used1, ed;
vector<array<int, 2>> par;
vector<int> U, V;

void dfs1(int x)
{
	used1[x] = 1;
	for (array<int, 2> &v : adj[x])
	{
		if (used1[v[0]]) continue;
		ed.push_back(v[1]);
		dfs1(v[0]);
	}
}

void process(vector<int> &v)
{
	used1.assign(N, 0);
	set<int> S;
	for (int x : v) 
	{
		used1[U[x]] = used1[V[x]] = 1;
		S.insert(U[x]), S.insert(V[x]);
		used[x] = 1;
	}
	ed.clear();
	for (int x : S) dfs1(x);
	int ind = ed.size();
	for (int x : v) ed.push_back(x);
	vector<array<int, 2>> v1;
	for (int i = ind; i < ed.size(); i++)
	{
		int y = ed[i];
		swap(ed[i], ed[(int)ed.size() - 1]);
		ed.pop_back();
		v1.push_back({count_common_roads(ed), y});
		ed.push_back(y);
		swap(ed[i], ed[(int)ed.size() - 1]);
	}
	sort(v1.begin(), v1.end());
	if (v1[0][0] == v1.back()[0]) return;
	for (array<int, 2> &x : v1)
	{
		if (x[0] == v1[0][0]) 
		{
			res.push_back(x[1]);
		}
	}
}

void dfs(int a)
{
	col[a] = 1;
	for (array<int, 2> &v : adj[a])
	{
		if (v[0] == par[a][0] || used[v[1]] || col[v[0]] == 2) continue;
		if (col[v[0]] == 1)
		{
			vector<int> x = {v[1]};
			int e = a;
			int s = v[0];
			while (1)
			{
				x.push_back(par[e][1]);
				e = par[e][0];
				if (e == s) break;
			}
			process(x);
		}
		else 
		{
			par[v[0]] = {a, v[1]};
			dfs(v[0]);
		}
	}
	col[a] = 2;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) 
{
	U = u, V = v;
	res.clear();
	col.assign(n, 0), par.assign(n, {-1, -1}), used.assign(u.size(), 0);
	N = n;
	for (int i = 0; i < n; i++) adj[i].clear();
	for (int i = 0; i < u.size(); i++) adj[u[i]].push_back({v[i], i}), adj[v[i]].push_back({u[i], i});
	while (res.size() < n - 1)
	{
		for (int i = 0; i < n; i++) col[i] = 0, par[i] = {-1, -1};
		for (int i = 0; i < n; i++)
		{
			if (!col[i]) dfs(i);
		}
	}
	sort(res.begin(), res.end());
	res.resize(unique(res.begin(), res.end()) - res.begin());
	return res;
}   

Compilation message (stderr)

simurgh.cpp: In function 'void process(std::vector<int>&)':
simurgh.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (int i = ind; i < ed.size(); i++)
      |                    ~~^~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for (int i = 0; i < u.size(); i++) adj[u[i]].push_back({v[i], i}), adj[v[i]].push_back({u[i], i});
      |                  ~~^~~~~~~~~~
simurgh.cpp:97:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |  while (res.size() < n - 1)
      |         ~~~~~~~~~~~^~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30