oj.uz

Submission #58192

# Submission time Handle Problem Language Result Execution time Memory
58192 2018-07-17T06:22:10 Z Crown Simurgh (IOI17_simurgh) C++14
30 / 100
 173 ms 6608 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)
{
	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 376 KB correct
2 Correct 2 ms 552 KB correct
3 Correct 2 ms 552 KB correct
4 Correct 2 ms 688 KB correct
5 Correct 3 ms 688 KB correct
6 Correct 2 ms 688 KB correct
7 Correct 3 ms 688 KB correct
8 Correct 3 ms 688 KB correct
9 Correct 2 ms 700 KB correct
10 Correct 2 ms 704 KB correct
11 Correct 3 ms 792 KB correct
12 Correct 2 ms 808 KB correct
13 Correct 2 ms 808 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 2 ms 552 KB correct
3 Correct 2 ms 552 KB correct
4 Correct 2 ms 688 KB correct
5 Correct 3 ms 688 KB correct
6 Correct 2 ms 688 KB correct
7 Correct 3 ms 688 KB correct
8 Correct 3 ms 688 KB correct
9 Correct 2 ms 700 KB correct
10 Correct 2 ms 704 KB correct
11 Correct 3 ms 792 KB correct
12 Correct 2 ms 808 KB correct
13 Correct 2 ms 808 KB correct
14 Correct 26 ms 912 KB correct
15 Correct 33 ms 920 KB correct
16 Correct 31 ms 1072 KB correct
17 Correct 35 ms 1072 KB correct
18 Correct 12 ms 1072 KB correct
19 Correct 42 ms 1124 KB correct
20 Correct 29 ms 1124 KB correct
21 Correct 25 ms 1124 KB correct
22 Correct 14 ms 1148 KB correct
23 Correct 10 ms 1148 KB correct
24 Correct 11 ms 1148 KB correct
25 Correct 3 ms 1148 KB correct
26 Correct 10 ms 1148 KB correct
27 Correct 12 ms 1148 KB correct
28 Correct 6 ms 1148 KB correct
29 Correct 4 ms 1148 KB correct
30 Correct 17 ms 1148 KB correct
31 Correct 17 ms 1148 KB correct
32 Correct 14 ms 1148 KB correct
33 Correct 15 ms 1160 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 2 ms 552 KB correct
3 Correct 2 ms 552 KB correct
4 Correct 2 ms 688 KB correct
5 Correct 3 ms 688 KB correct
6 Correct 2 ms 688 KB correct
7 Correct 3 ms 688 KB correct
8 Correct 3 ms 688 KB correct
9 Correct 2 ms 700 KB correct
10 Correct 2 ms 704 KB correct
11 Correct 3 ms 792 KB correct
12 Correct 2 ms 808 KB correct
13 Correct 2 ms 808 KB correct
14 Correct 26 ms 912 KB correct
15 Correct 33 ms 920 KB correct
16 Correct 31 ms 1072 KB correct
17 Correct 35 ms 1072 KB correct
18 Correct 12 ms 1072 KB correct
19 Correct 42 ms 1124 KB correct
20 Correct 29 ms 1124 KB correct
21 Correct 25 ms 1124 KB correct
22 Correct 14 ms 1148 KB correct
23 Correct 10 ms 1148 KB correct
24 Correct 11 ms 1148 KB correct
25 Correct 3 ms 1148 KB correct
26 Correct 10 ms 1148 KB correct
27 Correct 12 ms 1148 KB correct
28 Correct 6 ms 1148 KB correct
29 Correct 4 ms 1148 KB correct
30 Correct 17 ms 1148 KB correct
31 Correct 17 ms 1148 KB correct
32 Correct 14 ms 1148 KB correct
33 Correct 15 ms 1160 KB correct
34 Incorrect 130 ms 3008 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3008 KB correct
2 Correct 3 ms 3008 KB correct
3 Incorrect 173 ms 6608 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 376 KB correct
2 Correct 2 ms 552 KB correct
3 Correct 2 ms 552 KB correct
4 Correct 2 ms 688 KB correct
5 Correct 3 ms 688 KB correct
6 Correct 2 ms 688 KB correct
7 Correct 3 ms 688 KB correct
8 Correct 3 ms 688 KB correct
9 Correct 2 ms 700 KB correct
10 Correct 2 ms 704 KB correct
11 Correct 3 ms 792 KB correct
12 Correct 2 ms 808 KB correct
13 Correct 2 ms 808 KB correct
14 Correct 26 ms 912 KB correct
15 Correct 33 ms 920 KB correct
16 Correct 31 ms 1072 KB correct
17 Correct 35 ms 1072 KB correct
18 Correct 12 ms 1072 KB correct
19 Correct 42 ms 1124 KB correct
20 Correct 29 ms 1124 KB correct
21 Correct 25 ms 1124 KB correct
22 Correct 14 ms 1148 KB correct
23 Correct 10 ms 1148 KB correct
24 Correct 11 ms 1148 KB correct
25 Correct 3 ms 1148 KB correct
26 Correct 10 ms 1148 KB correct
27 Correct 12 ms 1148 KB correct
28 Correct 6 ms 1148 KB correct
29 Correct 4 ms 1148 KB correct
30 Correct 17 ms 1148 KB correct
31 Correct 17 ms 1148 KB correct
32 Correct 14 ms 1148 KB correct
33 Correct 15 ms 1160 KB correct
34 Incorrect 130 ms 3008 KB WA in grader: NO
35 Halted 0 ms 0 KB -