oj.uz

Submission #52065

# Submission time Handle Problem Language Result Execution time Memory
52065 2018-06-23T15:02:26 Z ernestvw Simurgh (IOI17_simurgh) C++11
30 / 100
 1073 ms 7164 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);
}
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 tmp = oldValue;
		int queee = query();
		memo[{id1, id2}] = memo[{id2, id1}] = queee - tmp;
		return queee;
	}
}

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(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 2 ms 248 KB correct
2 Correct 2 ms 356 KB correct
3 Correct 2 ms 560 KB correct
4 Correct 2 ms 620 KB correct
5 Correct 2 ms 620 KB correct
6 Correct 2 ms 620 KB correct
7 Correct 2 ms 620 KB correct
8 Correct 2 ms 692 KB correct
9 Correct 2 ms 692 KB correct
10 Correct 2 ms 692 KB correct
11 Correct 2 ms 716 KB correct
12 Correct 3 ms 716 KB correct
13 Correct 2 ms 716 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 2 ms 560 KB correct
4 Correct 2 ms 620 KB correct
5 Correct 2 ms 620 KB correct
6 Correct 2 ms 620 KB correct
7 Correct 2 ms 620 KB correct
8 Correct 2 ms 692 KB correct
9 Correct 2 ms 692 KB correct
10 Correct 2 ms 692 KB correct
11 Correct 2 ms 716 KB correct
12 Correct 3 ms 716 KB correct
13 Correct 2 ms 716 KB correct
14 Correct 37 ms 1016 KB correct
15 Correct 37 ms 1016 KB correct
16 Correct 40 ms 1144 KB correct
17 Correct 28 ms 1144 KB correct
18 Correct 8 ms 1144 KB correct
19 Correct 29 ms 1144 KB correct
20 Correct 28 ms 1144 KB correct
21 Correct 24 ms 1144 KB correct
22 Correct 10 ms 1144 KB correct
23 Correct 10 ms 1144 KB correct
24 Correct 7 ms 1144 KB correct
25 Correct 2 ms 1144 KB correct
26 Correct 9 ms 1144 KB correct
27 Correct 8 ms 1144 KB correct
28 Correct 4 ms 1144 KB correct
29 Correct 3 ms 1144 KB correct
30 Correct 8 ms 1144 KB correct
31 Correct 9 ms 1144 KB correct
32 Correct 10 ms 1144 KB correct
33 Correct 11 ms 1144 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 2 ms 560 KB correct
4 Correct 2 ms 620 KB correct
5 Correct 2 ms 620 KB correct
6 Correct 2 ms 620 KB correct
7 Correct 2 ms 620 KB correct
8 Correct 2 ms 692 KB correct
9 Correct 2 ms 692 KB correct
10 Correct 2 ms 692 KB correct
11 Correct 2 ms 716 KB correct
12 Correct 3 ms 716 KB correct
13 Correct 2 ms 716 KB correct
14 Correct 37 ms 1016 KB correct
15 Correct 37 ms 1016 KB correct
16 Correct 40 ms 1144 KB correct
17 Correct 28 ms 1144 KB correct
18 Correct 8 ms 1144 KB correct
19 Correct 29 ms 1144 KB correct
20 Correct 28 ms 1144 KB correct
21 Correct 24 ms 1144 KB correct
22 Correct 10 ms 1144 KB correct
23 Correct 10 ms 1144 KB correct
24 Correct 7 ms 1144 KB correct
25 Correct 2 ms 1144 KB correct
26 Correct 9 ms 1144 KB correct
27 Correct 8 ms 1144 KB correct
28 Correct 4 ms 1144 KB correct
29 Correct 3 ms 1144 KB correct
30 Correct 8 ms 1144 KB correct
31 Correct 9 ms 1144 KB correct
32 Correct 10 ms 1144 KB correct
33 Correct 11 ms 1144 KB correct
34 Incorrect 1073 ms 6072 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 6072 KB correct
2 Correct 2 ms 6072 KB correct
3 Incorrect 317 ms 7164 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 2 ms 560 KB correct
4 Correct 2 ms 620 KB correct
5 Correct 2 ms 620 KB correct
6 Correct 2 ms 620 KB correct
7 Correct 2 ms 620 KB correct
8 Correct 2 ms 692 KB correct
9 Correct 2 ms 692 KB correct
10 Correct 2 ms 692 KB correct
11 Correct 2 ms 716 KB correct
12 Correct 3 ms 716 KB correct
13 Correct 2 ms 716 KB correct
14 Correct 37 ms 1016 KB correct
15 Correct 37 ms 1016 KB correct
16 Correct 40 ms 1144 KB correct
17 Correct 28 ms 1144 KB correct
18 Correct 8 ms 1144 KB correct
19 Correct 29 ms 1144 KB correct
20 Correct 28 ms 1144 KB correct
21 Correct 24 ms 1144 KB correct
22 Correct 10 ms 1144 KB correct
23 Correct 10 ms 1144 KB correct
24 Correct 7 ms 1144 KB correct
25 Correct 2 ms 1144 KB correct
26 Correct 9 ms 1144 KB correct
27 Correct 8 ms 1144 KB correct
28 Correct 4 ms 1144 KB correct
29 Correct 3 ms 1144 KB correct
30 Correct 8 ms 1144 KB correct
31 Correct 9 ms 1144 KB correct
32 Correct 10 ms 1144 KB correct
33 Correct 11 ms 1144 KB correct
34 Incorrect 1073 ms 6072 KB WA in grader: NO
35 Halted 0 ms 0 KB -