답안 #52064 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52064	2018-06-23T14:53:26 Z	ernestvw	Simurgh (IOI17_simurgh)	C++11	30 / 100	862 ms	6028 KB

simurgh

#include <bits/stdc++.h>
using namespace std;

#include "simurgh.h"
//int count_common_roads(vector<int> r);

struct Arc {
	int u, v, i;
};

int nbNodes, nbArcs;
vector<Arc> arcs;
vector<Arc> adj[501];
map<pair<int, int>, int> idx;

bool vu[501];

set<int> roads;

int oldValue = -1;
int Q=0;
int query() {
	Q++;
	if(Q > 30000) exit(1);
	vector<int> quer;
	for(int i : roads) quer.push_back(i);
	return oldValue = count_common_roads(quer);
}

void traverse(int u, int i) {
	if(vu[u]) return;
	vu[u] = 1;
	if(i != -1) roads.insert(i);
	for(Arc a : adj[u])
		if(!vu[a.v])
			traverse(a.v, a.i);
}

void buildTree() {
	for(int i = 0; i < nbNodes; i++) vu[i] = false;
	traverse(0, -1);
}

int parent[501*250];
int find(int x) {
	return x == parent[x] ? x : (parent[x] = find(parent[x]));
}
void merge(int x, int y) {
	parent[find(x)] = find(y);
}

const int ROYAL = 500*250+1;
const int BAD = 500*250+2;

bool good(int i) {
	return find(i) == find(ROYAL);	
}
bool bad(int i) {
	return find(i) == find(BAD);
}

void init() {
	for(int i = 0; i < nbArcs; i++) parent[i] = i;
	parent[ROYAL] = ROYAL;
	parent[BAD] = BAD;
}

vector<int> path, curr;
bool found=0;

void dfs(int u, int target, int p) {
	if(u == target) {
		found=1;
		path = curr;
	}
	if(found) return;
	for(Arc a : adj[u]) {
		if(!roads.count(a.i) or a.v == p) continue;
		curr.push_back(a.i);
		dfs(a.v, target, u);
		curr.pop_back();
	}
}

vector<int> findCycle(int u, int v) {
	path.clear(), curr.clear(), found=0;
	dfs(u, v, -1);
	return path;
}

void findSol() {
	init();
	for(Arc a : arcs) {
		if(roads.count(a.i)) continue;
		if(bad(a.i)) continue;
		int i = a.i;
		int u = a.u;
		int v = a.v;
		vector<int> cycle = findCycle(u, v);
		for(int id : cycle) {
			int old = oldValue;
			roads.insert(i);
			roads.erase(id);
			int nouv = query();
			if(nouv > old) {
				merge(ROYAL, i);
				merge(BAD, id);
				break;
			}
			else if(nouv == old) {
				merge(id, i);
				roads.insert(id);
				roads.erase(i);
				oldValue = old;
			}
			else {
				merge(id, ROYAL);
				merge(i, BAD);
				roads.insert(id);
				roads.erase(i);
				oldValue = old;
				break;
			}
		}
	}
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	nbNodes = n;
	nbArcs = (int)u.size();
	arcs.clear();
	for(int i = 0; i < nbArcs; i++) {
		arcs.push_back({u[i], v[i], i});
		adj[u[i]].push_back({u[i], v[i], i});
		adj[v[i]].push_back({v[i], u[i], i});
	}
	vector<int> ans;
	buildTree();
	query();
	findSol();
	for(int i : roads) ans.push_back(i);
	return ans;
}
/*
bool GOLDEN[501*250];
int count_common_roads(vector<int> r) {
	int cnt(0);
	for(int i:r)if(GOLDEN[i])cnt++;
	return cnt;
}

int main() {
	int T=1;
	while(T--){
	int n, m;cin>>n>>m;
	vector<int>u(m), v(m);
	for(int i=0;i<m;i++){
		cin>>u[i]>>v[i];
	}
	for(int i=0;i<m;i++)GOLDEN[i]=0;
	for(int i=0;i<n-1;i++){int s;cin>>s;GOLDEN[s]=1;}
	vector<int> sol = find_roads(n, u, v);
	for(int i : sol) {
		cout << i << " ";
	}
	cout << endl;
	}
}
*/

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	correct
2	Correct	2 ms	356 KB	correct
3	Correct	3 ms	408 KB	correct
4	Correct	2 ms	460 KB	correct
5	Correct	2 ms	460 KB	correct
6	Correct	3 ms	460 KB	correct
7	Correct	2 ms	460 KB	correct
8	Correct	2 ms	508 KB	correct
9	Correct	2 ms	512 KB	correct
10	Correct	3 ms	520 KB	correct
11	Correct	2 ms	596 KB	correct
12	Correct	3 ms	724 KB	correct
13	Correct	2 ms	724 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	correct
2	Correct	2 ms	356 KB	correct
3	Correct	3 ms	408 KB	correct
4	Correct	2 ms	460 KB	correct
5	Correct	2 ms	460 KB	correct
6	Correct	3 ms	460 KB	correct
7	Correct	2 ms	460 KB	correct
8	Correct	2 ms	508 KB	correct
9	Correct	2 ms	512 KB	correct
10	Correct	3 ms	520 KB	correct
11	Correct	2 ms	596 KB	correct
12	Correct	3 ms	724 KB	correct
13	Correct	2 ms	724 KB	correct
14	Correct	42 ms	724 KB	correct
15	Correct	40 ms	724 KB	correct
16	Correct	35 ms	724 KB	correct
17	Correct	25 ms	724 KB	correct
18	Correct	8 ms	724 KB	correct
19	Correct	34 ms	724 KB	correct
20	Correct	23 ms	748 KB	correct
21	Correct	23 ms	748 KB	correct
22	Correct	11 ms	748 KB	correct
23	Correct	9 ms	748 KB	correct
24	Correct	7 ms	748 KB	correct
25	Correct	2 ms	748 KB	correct
26	Correct	8 ms	748 KB	correct
27	Correct	7 ms	748 KB	correct
28	Correct	4 ms	748 KB	correct
29	Correct	3 ms	748 KB	correct
30	Correct	7 ms	748 KB	correct
31	Correct	7 ms	748 KB	correct
32	Correct	7 ms	748 KB	correct
33	Correct	7 ms	748 KB	correct

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	correct
2	Correct	2 ms	356 KB	correct
3	Correct	3 ms	408 KB	correct
4	Correct	2 ms	460 KB	correct
5	Correct	2 ms	460 KB	correct
6	Correct	3 ms	460 KB	correct
7	Correct	2 ms	460 KB	correct
8	Correct	2 ms	508 KB	correct
9	Correct	2 ms	512 KB	correct
10	Correct	3 ms	520 KB	correct
11	Correct	2 ms	596 KB	correct
12	Correct	3 ms	724 KB	correct
13	Correct	2 ms	724 KB	correct
14	Correct	42 ms	724 KB	correct
15	Correct	40 ms	724 KB	correct
16	Correct	35 ms	724 KB	correct
17	Correct	25 ms	724 KB	correct
18	Correct	8 ms	724 KB	correct
19	Correct	34 ms	724 KB	correct
20	Correct	23 ms	748 KB	correct
21	Correct	23 ms	748 KB	correct
22	Correct	11 ms	748 KB	correct
23	Correct	9 ms	748 KB	correct
24	Correct	7 ms	748 KB	correct
25	Correct	2 ms	748 KB	correct
26	Correct	8 ms	748 KB	correct
27	Correct	7 ms	748 KB	correct
28	Correct	4 ms	748 KB	correct
29	Correct	3 ms	748 KB	correct
30	Correct	7 ms	748 KB	correct
31	Correct	7 ms	748 KB	correct
32	Correct	7 ms	748 KB	correct
33	Correct	7 ms	748 KB	correct
34	Runtime error	862 ms	2360 KB	Execution failed because the return code was nonzero
35	Halted	0 ms	0 KB	-

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2360 KB	correct
2	Correct	2 ms	2360 KB	correct
3	Incorrect	346 ms	6028 KB	WA in grader: NO
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	correct
2	Correct	2 ms	356 KB	correct
3	Correct	3 ms	408 KB	correct
4	Correct	2 ms	460 KB	correct
5	Correct	2 ms	460 KB	correct
6	Correct	3 ms	460 KB	correct
7	Correct	2 ms	460 KB	correct
8	Correct	2 ms	508 KB	correct
9	Correct	2 ms	512 KB	correct
10	Correct	3 ms	520 KB	correct
11	Correct	2 ms	596 KB	correct
12	Correct	3 ms	724 KB	correct
13	Correct	2 ms	724 KB	correct
14	Correct	42 ms	724 KB	correct
15	Correct	40 ms	724 KB	correct
16	Correct	35 ms	724 KB	correct
17	Correct	25 ms	724 KB	correct
18	Correct	8 ms	724 KB	correct
19	Correct	34 ms	724 KB	correct
20	Correct	23 ms	748 KB	correct
21	Correct	23 ms	748 KB	correct
22	Correct	11 ms	748 KB	correct
23	Correct	9 ms	748 KB	correct
24	Correct	7 ms	748 KB	correct
25	Correct	2 ms	748 KB	correct
26	Correct	8 ms	748 KB	correct
27	Correct	7 ms	748 KB	correct
28	Correct	4 ms	748 KB	correct
29	Correct	3 ms	748 KB	correct
30	Correct	7 ms	748 KB	correct
31	Correct	7 ms	748 KB	correct
32	Correct	7 ms	748 KB	correct
33	Correct	7 ms	748 KB	correct
34	Runtime error	862 ms	2360 KB	Execution failed because the return code was nonzero
35	Halted	0 ms	0 KB	-

답안 #52064

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