oj.uz

Submission #58194

# Submission time Handle Problem Language Result Execution time Memory
58194 2018-07-17T06:24:33 Z Crown Simurgh (IOI17_simurgh) C++14
30 / 100
 162 ms 5888 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;
		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;
	}
	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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB correct
2 Correct 3 ms 1000 KB correct
3 Correct 3 ms 1000 KB correct
4 Correct 4 ms 1000 KB correct
5 Correct 3 ms 1116 KB correct
6 Correct 2 ms 1188 KB correct
7 Correct 3 ms 1188 KB correct
8 Correct 3 ms 1212 KB correct
9 Correct 3 ms 1212 KB correct
10 Correct 1 ms 1212 KB correct
11 Correct 4 ms 1212 KB correct
12 Correct 3 ms 1212 KB correct
13 Correct 3 ms 1212 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB correct
2 Correct 3 ms 1000 KB correct
3 Correct 3 ms 1000 KB correct
4 Correct 4 ms 1000 KB correct
5 Correct 3 ms 1116 KB correct
6 Correct 2 ms 1188 KB correct
7 Correct 3 ms 1188 KB correct
8 Correct 3 ms 1212 KB correct
9 Correct 3 ms 1212 KB correct
10 Correct 1 ms 1212 KB correct
11 Correct 4 ms 1212 KB correct
12 Correct 3 ms 1212 KB correct
13 Correct 3 ms 1212 KB correct
14 Correct 30 ms 1260 KB correct
15 Correct 28 ms 1260 KB correct
16 Correct 36 ms 1336 KB correct
17 Correct 26 ms 1336 KB correct
18 Correct 11 ms 1336 KB correct
19 Correct 26 ms 1336 KB correct
20 Correct 28 ms 1336 KB correct
21 Correct 23 ms 1336 KB correct
22 Correct 12 ms 1336 KB correct
23 Correct 11 ms 1336 KB correct
24 Correct 15 ms 1336 KB correct
25 Correct 2 ms 1336 KB correct
26 Correct 10 ms 1336 KB correct
27 Correct 12 ms 1336 KB correct
28 Correct 7 ms 1336 KB correct
29 Correct 5 ms 1336 KB correct
30 Correct 23 ms 1336 KB correct
31 Correct 17 ms 1336 KB correct
32 Correct 19 ms 1336 KB correct
33 Correct 19 ms 1336 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB correct
2 Correct 3 ms 1000 KB correct
3 Correct 3 ms 1000 KB correct
4 Correct 4 ms 1000 KB correct
5 Correct 3 ms 1116 KB correct
6 Correct 2 ms 1188 KB correct
7 Correct 3 ms 1188 KB correct
8 Correct 3 ms 1212 KB correct
9 Correct 3 ms 1212 KB correct
10 Correct 1 ms 1212 KB correct
11 Correct 4 ms 1212 KB correct
12 Correct 3 ms 1212 KB correct
13 Correct 3 ms 1212 KB correct
14 Correct 30 ms 1260 KB correct
15 Correct 28 ms 1260 KB correct
16 Correct 36 ms 1336 KB correct
17 Correct 26 ms 1336 KB correct
18 Correct 11 ms 1336 KB correct
19 Correct 26 ms 1336 KB correct
20 Correct 28 ms 1336 KB correct
21 Correct 23 ms 1336 KB correct
22 Correct 12 ms 1336 KB correct
23 Correct 11 ms 1336 KB correct
24 Correct 15 ms 1336 KB correct
25 Correct 2 ms 1336 KB correct
26 Correct 10 ms 1336 KB correct
27 Correct 12 ms 1336 KB correct
28 Correct 7 ms 1336 KB correct
29 Correct 5 ms 1336 KB correct
30 Correct 23 ms 1336 KB correct
31 Correct 17 ms 1336 KB correct
32 Correct 19 ms 1336 KB correct
33 Correct 19 ms 1336 KB correct
34 Incorrect 162 ms 2940 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2940 KB correct
2 Correct 3 ms 2940 KB correct
3 Incorrect 142 ms 5888 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 1000 KB correct
3 Correct 3 ms 1000 KB correct
4 Correct 4 ms 1000 KB correct
5 Correct 3 ms 1116 KB correct
6 Correct 2 ms 1188 KB correct
7 Correct 3 ms 1188 KB correct
8 Correct 3 ms 1212 KB correct
9 Correct 3 ms 1212 KB correct
10 Correct 1 ms 1212 KB correct
11 Correct 4 ms 1212 KB correct
12 Correct 3 ms 1212 KB correct
13 Correct 3 ms 1212 KB correct
14 Correct 30 ms 1260 KB correct
15 Correct 28 ms 1260 KB correct
16 Correct 36 ms 1336 KB correct
17 Correct 26 ms 1336 KB correct
18 Correct 11 ms 1336 KB correct
19 Correct 26 ms 1336 KB correct
20 Correct 28 ms 1336 KB correct
21 Correct 23 ms 1336 KB correct
22 Correct 12 ms 1336 KB correct
23 Correct 11 ms 1336 KB correct
24 Correct 15 ms 1336 KB correct
25 Correct 2 ms 1336 KB correct
26 Correct 10 ms 1336 KB correct
27 Correct 12 ms 1336 KB correct
28 Correct 7 ms 1336 KB correct
29 Correct 5 ms 1336 KB correct
30 Correct 23 ms 1336 KB correct
31 Correct 17 ms 1336 KB correct
32 Correct 19 ms 1336 KB correct
33 Correct 19 ms 1336 KB correct
34 Incorrect 162 ms 2940 KB WA in grader: NO
35 Halted 0 ms 0 KB -