답안 #58194 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
58194	2018-07-17T06:24:33 Z	Crown	Simurgh (IOI17_simurgh)	C++14	30 / 100	162 ms	5888 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)
{
	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

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

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

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

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

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

답안 #58194

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