oj.uz

Submission #58510

# Submission time Handle Problem Language Result Execution time Memory
58510 2018-07-18T04:29:46 Z Crown Simurgh (IOI17_simurgh) C++14
0 / 100
 145 ms 6320 KB 
#include "simurgh.h"

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

// int count_common_roads(vector<int> vec)

const int maxn = 505;
const int maxm = maxn*maxn/2;

int n, m;
int edgeID[maxn][maxn];
vector<int> U, V;

vector<int> adj[maxn];

int par[maxn];
bool vis[maxn];
int dep[maxn];
int tree_score[maxm];

bool isInTree[maxm];
bool isNotBridge[maxm];
bool res[maxm];

vector<int> backedges; 

vector<int> output;

void find_tree(int u = 0, int p = -1)
{
	if(p != -1) par[u] = p;	
	vis[u] = true;
	for(auto v : adj[u])
	{
		if(!vis[v])
		{
			dep[v] = dep[u]+1;
			find_tree(v, u);
			isInTree[edgeID[u][v]] = true;
			output.push_back(edgeID[u][v]);
		}
		else if(v != p)
		{
			backedges.pb(edgeID[u][v]);
		}
	}
}

bool cmp(int a, int b)
{
	int ua = U[a], ub = U[b];
	int va = V[a], vb = V[b];
	return min(dep[ua], dep[va])< min(dep[ub], dep[vb]);
}

void delete_from_output(int u)
{
	vector<int> nou;
	for(auto x : output)
	{
		if(x == u) continue;
		nou.pb(x);
	}
	output = nou; 
}

void add_to_output(int u)
{
	output.pb(u);
}

int ask()
{
	return count_common_roads(output);
}
vector<int> find_roads(int _n, vector<int> _u, vector<int> _v)
{
	memset(tree_score, -1, sizeof tree_score);
	n = _n; m = _u.size();
	U = _u; V = _v;
	for(int i = 0; i< m; i++)
	{
		int u = U[i], v = V[i];
		edgeID[u][v] = edgeID[v][u] = i;
		adj[u].pb(v); adj[v].pb(u);
	}
	dep[0] = 1; find_tree();
	sort(backedges.begin(), backedges.end());
	backedges.resize(unique(backedges.begin(), backedges.end())-backedges.begin());
	sort(backedges.begin(), backedges.end(), cmp);
	int base_score = ask();
	for(auto edge : backedges)
	{
		int u = U[edge], v = V[edge];
		if(dep[u]< dep[v]) swap(u, v);
		int cur = u;
		
		int sample = -1;
		bool not_asked = true;
		while(cur != v)
		{
			int tp = par[cur];
			int id = edgeID[cur][tp];
			if(tree_score[id] != -1)
			{
				not_asked = false;
				sample = id;
			}
			cur = tp;
		}
		
		if(not_asked)
		{
			cur = u;
			add_to_output(edge);
			int mn = base_score, mx = base_score;
			while(cur != v)
			{
				int tp = par[cur];
				int id = edgeID[cur][tp];
				isNotBridge[id] = true;
				delete_from_output(id);
				tree_score[id] = ask();
				mn = min(tree_score[id], mn);
				mx = max(tree_score[id], mx);
				add_to_output(id);
				cur = tp;
			}
			delete_from_output(edge);
			cur = u;
			while(cur != v)
			{
				int tp = par[cur];
				int id = edgeID[cur][tp];
				if(mn == mx) res[id] = false;
				else if(tree_score[id] == mn) res[id] = true;
				else res[id] = false;
				cur = tp;
			}
			if(mn != mx && base_score == mn) res[edge] = true;
		}
		else
		{
			delete_from_output(sample);
			add_to_output(edge);
			int mod_score = base_score-res[sample];
			int temp = ask();
			if(temp> mod_score) res[edge] = true;
			else res[edge] = false;
			add_to_output(sample);
			cur = u;
			while(cur != v)
			{
				int tp = par[cur];
				int id = edgeID[cur][tp];
				if(tree_score[edge] != -1)
				{
					cur = tp; continue;
				}
				delete_from_output(id);
				int temp = ask();
				int mod_score = base_score+res[edge];
				if(temp< mod_score) res[id] = true;
				else res[id] = false;
				add_to_output(id);
				cur = tp;
			}
			delete_from_output(edge);
		}
	}
	output.clear();
	for(int i = 0; i< m; i++)
	{
		if((!isNotBridge[i] and isInTree[i]) or res[i]) output.pb(i);
	}
	assert(ask() == n-1);
	return output;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB correct
2 Correct 3 ms 964 KB correct
3 Correct 4 ms 1068 KB correct
4 Incorrect 3 ms 1068 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB correct
2 Correct 3 ms 964 KB correct
3 Correct 4 ms 1068 KB correct
4 Incorrect 3 ms 1068 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB correct
2 Correct 3 ms 964 KB correct
3 Correct 4 ms 1068 KB correct
4 Incorrect 3 ms 1068 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1128 KB correct
2 Correct 3 ms 1128 KB correct
3 Incorrect 145 ms 6320 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB correct
2 Correct 3 ms 964 KB correct
3 Correct 4 ms 1068 KB correct
4 Incorrect 3 ms 1068 KB WA in grader: NO
5 Halted 0 ms 0 KB -