oj.uz

Submission #52064

# Submission time Handle Problem Language Result Execution time Memory
52064 2018-06-23T14:53:26 Z ernestvw Simurgh (IOI17_simurgh) C++11
30 / 100
 862 ms 6028 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -