oj.uz

Submission #977708

# Submission time Handle Problem Language Result Execution time Memory
977708 2024-05-08T09:53:11 Z JwFXoiz Simurgh (IOI17_simurgh) C++14
0 / 100
 3000 ms 504 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 348 KB correct
4 Correct 1 ms 348 KB correct
5 Correct 1 ms 344 KB correct
6 Correct 1 ms 348 KB correct
7 Execution timed out 3020 ms 504 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 348 KB correct
4 Correct 1 ms 348 KB correct
5 Correct 1 ms 344 KB correct
6 Correct 1 ms 348 KB correct
7 Execution timed out 3020 ms 504 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 348 KB correct
4 Correct 1 ms 348 KB correct
5 Correct 1 ms 344 KB correct
6 Correct 1 ms 348 KB correct
7 Execution timed out 3020 ms 504 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3003 ms 504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 348 KB correct
4 Correct 1 ms 348 KB correct
5 Correct 1 ms 344 KB correct
6 Correct 1 ms 348 KB correct
7 Execution timed out 3020 ms 504 KB Time limit exceeded
8 Halted 0 ms 0 KB -