oj.uz

Submission #52066

# Submission time Handle Problem Language Result Execution time Memory
52066 2018-06-23T15:05:40 Z ernestvw Simurgh (IOI17_simurgh) C++11
30 / 100
 3000 ms 18056 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;
}

map<pair<int, int>, int> memo;
int Query(int id1, int id2) {
	if(memo.count({id1, id2})) {
		oldValue += memo[{id1, id2}];
		return oldValue;
	}
	else {
		int queee(-1);
		if(find(id1) == find(id2)) queee = oldValue;
		else queee = query();
		int tmp = oldValue;
		memo[{id1, id2}] = memo[{id2, id1}] = queee - tmp;
		return queee;
	}
}

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(i, id);
			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 3 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 416 KB correct
4 Correct 2 ms 468 KB correct
5 Correct 3 ms 468 KB correct
6 Correct 2 ms 468 KB correct
7 Correct 2 ms 516 KB correct
8 Correct 2 ms 592 KB correct
9 Correct 2 ms 712 KB correct
10 Correct 3 ms 712 KB correct
11 Correct 2 ms 712 KB correct
12 Correct 3 ms 712 KB correct
13 Correct 2 ms 712 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 416 KB correct
4 Correct 2 ms 468 KB correct
5 Correct 3 ms 468 KB correct
6 Correct 2 ms 468 KB correct
7 Correct 2 ms 516 KB correct
8 Correct 2 ms 592 KB correct
9 Correct 2 ms 712 KB correct
10 Correct 3 ms 712 KB correct
11 Correct 2 ms 712 KB correct
12 Correct 3 ms 712 KB correct
13 Correct 2 ms 712 KB correct
14 Correct 37 ms 1004 KB correct
15 Correct 39 ms 1048 KB correct
16 Correct 40 ms 1132 KB correct
17 Correct 29 ms 1132 KB correct
18 Correct 7 ms 1132 KB correct
19 Correct 27 ms 1132 KB correct
20 Correct 24 ms 1132 KB correct
21 Correct 23 ms 1132 KB correct
22 Correct 10 ms 1132 KB correct
23 Correct 9 ms 1132 KB correct
24 Correct 8 ms 1132 KB correct
25 Correct 2 ms 1132 KB correct
26 Correct 11 ms 1132 KB correct
27 Correct 7 ms 1132 KB correct
28 Correct 4 ms 1132 KB correct
29 Correct 2 ms 1132 KB correct
30 Correct 8 ms 1132 KB correct
31 Correct 8 ms 1132 KB correct
32 Correct 10 ms 1132 KB correct
33 Correct 10 ms 1132 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 416 KB correct
4 Correct 2 ms 468 KB correct
5 Correct 3 ms 468 KB correct
6 Correct 2 ms 468 KB correct
7 Correct 2 ms 516 KB correct
8 Correct 2 ms 592 KB correct
9 Correct 2 ms 712 KB correct
10 Correct 3 ms 712 KB correct
11 Correct 2 ms 712 KB correct
12 Correct 3 ms 712 KB correct
13 Correct 2 ms 712 KB correct
14 Correct 37 ms 1004 KB correct
15 Correct 39 ms 1048 KB correct
16 Correct 40 ms 1132 KB correct
17 Correct 29 ms 1132 KB correct
18 Correct 7 ms 1132 KB correct
19 Correct 27 ms 1132 KB correct
20 Correct 24 ms 1132 KB correct
21 Correct 23 ms 1132 KB correct
22 Correct 10 ms 1132 KB correct
23 Correct 9 ms 1132 KB correct
24 Correct 8 ms 1132 KB correct
25 Correct 2 ms 1132 KB correct
26 Correct 11 ms 1132 KB correct
27 Correct 7 ms 1132 KB correct
28 Correct 4 ms 1132 KB correct
29 Correct 2 ms 1132 KB correct
30 Correct 8 ms 1132 KB correct
31 Correct 8 ms 1132 KB correct
32 Correct 10 ms 1132 KB correct
33 Correct 10 ms 1132 KB correct
34 Execution timed out 3023 ms 8996 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8996 KB correct
2 Correct 2 ms 8996 KB correct
3 Execution timed out 3039 ms 18056 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 2 ms 416 KB correct
4 Correct 2 ms 468 KB correct
5 Correct 3 ms 468 KB correct
6 Correct 2 ms 468 KB correct
7 Correct 2 ms 516 KB correct
8 Correct 2 ms 592 KB correct
9 Correct 2 ms 712 KB correct
10 Correct 3 ms 712 KB correct
11 Correct 2 ms 712 KB correct
12 Correct 3 ms 712 KB correct
13 Correct 2 ms 712 KB correct
14 Correct 37 ms 1004 KB correct
15 Correct 39 ms 1048 KB correct
16 Correct 40 ms 1132 KB correct
17 Correct 29 ms 1132 KB correct
18 Correct 7 ms 1132 KB correct
19 Correct 27 ms 1132 KB correct
20 Correct 24 ms 1132 KB correct
21 Correct 23 ms 1132 KB correct
22 Correct 10 ms 1132 KB correct
23 Correct 9 ms 1132 KB correct
24 Correct 8 ms 1132 KB correct
25 Correct 2 ms 1132 KB correct
26 Correct 11 ms 1132 KB correct
27 Correct 7 ms 1132 KB correct
28 Correct 4 ms 1132 KB correct
29 Correct 2 ms 1132 KB correct
30 Correct 8 ms 1132 KB correct
31 Correct 8 ms 1132 KB correct
32 Correct 10 ms 1132 KB correct
33 Correct 10 ms 1132 KB correct
34 Execution timed out 3023 ms 8996 KB Time limit exceeded
35 Halted 0 ms 0 KB -