oj.uz

Submission #838246

# Submission time Handle Problem Language Result Execution time Memory
838246 2023-08-26T12:01:32 Z Johann Simurgh (IOI17_simurgh) C++14
0 / 100
 1 ms 468 KB 
#include "simurgh.h"
#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N;
vi U, V;
vvpii adj;
vi goldenTree;
const int NOTHING = 0;
const int FRONTIER = 1;
const int EXPLORED = 2;
vi status;
vvi edgesToCandidates;
vi tmpTree;
vi belongs;
int cntQueries;

vi askEdges;

void buildTree(int v)
{
	for (pii e : adj[v])
		if (status[e.first] == NOTHING && belongs[e.first] == -1)
		{
			belongs[e.first] = belongs[v];
			tmpTree.push_back(e.second);
			buildTree(e.first);
		}
		else if (status[e.first] == FRONTIER)
			edgesToCandidates[belongs[v]].push_back(e.second);
}

void findGoldenTree()
{
	if (sz(goldenTree) == N - 1)
		return;
	int groups = 0;
	edgesToCandidates.clear();
	tmpTree = vi(all(goldenTree));
	belongs.assign(N, -1);
	for (int v = 0; v < N; ++v)
		if (status[v] == NOTHING && belongs[v] == -1)
		{
			belongs[v] = groups++;
			edgesToCandidates.push_back(vi());
			buildTree(v);
			assert(!edgesToCandidates.empty());
		}

	vi toAdd;
	for (int g = 0; g < groups; ++g)
	{
		for (int g2 = 0; g2 < groups; ++g2)
			if (g2 != g)
				tmpTree.push_back(edgesToCandidates[g2].front());

		vi record(sz(edgesToCandidates[g]));
		for (int i = 0; i < sz(edgesToCandidates[g]); ++i)
		{
			tmpTree.push_back(edgesToCandidates[g][i]);
			++cntQueries;
			assert(!askEdges[edgesToCandidates[g][i]]);
			askEdges[edgesToCandidates[g][i]] = true;
			// assert(cntQueries <= 30000);
			record[i] = count_common_roads(tmpTree);
			tmpTree.pop_back();
		}

		int maxi = *max_element(all(record));
		for (int i = 0; i < sz(edgesToCandidates[g]); ++i)
			if (maxi == record[i])
				toAdd.push_back(edgesToCandidates[g][i]);

		for (int g2 = 0; g2 < groups; ++g2)
			if (g2 != g)
				tmpTree.pop_back();
	}

	// assert(!toAdd.empty());
	for (int x : toAdd)
	{
		if (status[U[x]] != NOTHING)
			status[U[x]] = EXPLORED, status[V[x]] = FRONTIER;
		else
			status[V[x]] = EXPLORED, status[U[x]] = FRONTIER;
		goldenTree.push_back(x);
	}
	findGoldenTree();
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v)
{
	N = n;
	U = u, V = v;
	adj = vvpii(n);
	for (int i = 0; i < sz(u); ++i)
		adj[u[i]].push_back({v[i], i}), adj[v[i]].push_back({u[i], i});

	cntQueries = 0;
	askEdges.assign(sz(u), 0);

	goldenTree.clear();
	status.assign(n, NOTHING);
	status[0] = FRONTIER;
	findGoldenTree();

	// cout << cntQueries << endl;

	return goldenTree;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Runtime error 1 ms 340 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Runtime error 1 ms 340 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Runtime error 1 ms 340 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Runtime error 1 ms 340 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -