답안 #58192 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58192	2018-07-17T06:22:10 Z	Crown	Simurgh (IOI17_simurgh)	C++14	30 / 100	173 ms	6608 KB

simurgh

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #58192

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0