oj.uz

Submission #52063

# Submission time Handle Problem Language Result Execution time Memory
52063 2018-06-23T14:34:56 Z ernestvw Simurgh (IOI17_simurgh) C++11
30 / 100
 891 ms 7172 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 query() {
	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 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 552 KB correct
4 Correct 2 ms 552 KB correct
5 Correct 3 ms 596 KB correct
6 Correct 2 ms 660 KB correct
7 Correct 2 ms 660 KB correct
8 Correct 2 ms 660 KB correct
9 Correct 2 ms 660 KB correct
10 Correct 2 ms 660 KB correct
11 Correct 2 ms 660 KB correct
12 Correct 2 ms 660 KB correct
13 Correct 3 ms 684 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 552 KB correct
4 Correct 2 ms 552 KB correct
5 Correct 3 ms 596 KB correct
6 Correct 2 ms 660 KB correct
7 Correct 2 ms 660 KB correct
8 Correct 2 ms 660 KB correct
9 Correct 2 ms 660 KB correct
10 Correct 2 ms 660 KB correct
11 Correct 2 ms 660 KB correct
12 Correct 2 ms 660 KB correct
13 Correct 3 ms 684 KB correct
14 Correct 36 ms 684 KB correct
15 Correct 36 ms 820 KB correct
16 Correct 37 ms 876 KB correct
17 Correct 25 ms 900 KB correct
18 Correct 7 ms 900 KB correct
19 Correct 29 ms 900 KB correct
20 Correct 24 ms 988 KB correct
21 Correct 22 ms 988 KB correct
22 Correct 11 ms 988 KB correct
23 Correct 9 ms 988 KB correct
24 Correct 9 ms 988 KB correct
25 Correct 3 ms 988 KB correct
26 Correct 9 ms 988 KB correct
27 Correct 12 ms 988 KB correct
28 Correct 5 ms 988 KB correct
29 Correct 3 ms 988 KB correct
30 Correct 8 ms 988 KB correct
31 Correct 10 ms 988 KB correct
32 Correct 9 ms 988 KB correct
33 Correct 10 ms 988 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 552 KB correct
4 Correct 2 ms 552 KB correct
5 Correct 3 ms 596 KB correct
6 Correct 2 ms 660 KB correct
7 Correct 2 ms 660 KB correct
8 Correct 2 ms 660 KB correct
9 Correct 2 ms 660 KB correct
10 Correct 2 ms 660 KB correct
11 Correct 2 ms 660 KB correct
12 Correct 2 ms 660 KB correct
13 Correct 3 ms 684 KB correct
14 Correct 36 ms 684 KB correct
15 Correct 36 ms 820 KB correct
16 Correct 37 ms 876 KB correct
17 Correct 25 ms 900 KB correct
18 Correct 7 ms 900 KB correct
19 Correct 29 ms 900 KB correct
20 Correct 24 ms 988 KB correct
21 Correct 22 ms 988 KB correct
22 Correct 11 ms 988 KB correct
23 Correct 9 ms 988 KB correct
24 Correct 9 ms 988 KB correct
25 Correct 3 ms 988 KB correct
26 Correct 9 ms 988 KB correct
27 Correct 12 ms 988 KB correct
28 Correct 5 ms 988 KB correct
29 Correct 3 ms 988 KB correct
30 Correct 8 ms 988 KB correct
31 Correct 10 ms 988 KB correct
32 Correct 9 ms 988 KB correct
33 Correct 10 ms 988 KB correct
34 Incorrect 891 ms 2936 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 2936 KB correct
2 Correct 2 ms 2936 KB correct
3 Incorrect 278 ms 7172 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 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 552 KB correct
4 Correct 2 ms 552 KB correct
5 Correct 3 ms 596 KB correct
6 Correct 2 ms 660 KB correct
7 Correct 2 ms 660 KB correct
8 Correct 2 ms 660 KB correct
9 Correct 2 ms 660 KB correct
10 Correct 2 ms 660 KB correct
11 Correct 2 ms 660 KB correct
12 Correct 2 ms 660 KB correct
13 Correct 3 ms 684 KB correct
14 Correct 36 ms 684 KB correct
15 Correct 36 ms 820 KB correct
16 Correct 37 ms 876 KB correct
17 Correct 25 ms 900 KB correct
18 Correct 7 ms 900 KB correct
19 Correct 29 ms 900 KB correct
20 Correct 24 ms 988 KB correct
21 Correct 22 ms 988 KB correct
22 Correct 11 ms 988 KB correct
23 Correct 9 ms 988 KB correct
24 Correct 9 ms 988 KB correct
25 Correct 3 ms 988 KB correct
26 Correct 9 ms 988 KB correct
27 Correct 12 ms 988 KB correct
28 Correct 5 ms 988 KB correct
29 Correct 3 ms 988 KB correct
30 Correct 8 ms 988 KB correct
31 Correct 10 ms 988 KB correct
32 Correct 9 ms 988 KB correct
33 Correct 10 ms 988 KB correct
34 Incorrect 891 ms 2936 KB WA in grader: NO
35 Halted 0 ms 0 KB -