oj.uz

Submission #52072

# Submission time Handle Problem Language Result Execution time Memory
52072 2018-06-23T16:07:46 Z ernestvw Simurgh (IOI17_simurgh) C++11
30 / 100
 3000 ms 108024 KB 
/*
	Time: O(N^4)
	Queries: Q <= 30000
	Score: 30/100
*/
#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;
	}
}

vector<int> Path[501][501];
vector<int> act;
void Dfs(int u, int p, int a) {
	if(vu[u]) return;
	Path[a][u] = act;
	vu[u] = 1;
	for(Arc A : adj[u]) {
		if(!roads.count(A.i) or A.v == p) continue;
		act.push_back(A.i);
		Dfs(A.v, u, a);
		act.pop_back();
	}
}
void iniTree() {
	for(int i=0;i<nbNodes;i++){
		for(int j=0;j<nbNodes;j++)vu[j]=0;
		act.clear();
		Dfs(i, -1, i);
	}
}
vector<int> findCycle2(int u, int v) {
	return Path[u][v];
}

void findSol() {
	init();
	iniTree();
	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); //this line has to be optimized to O(n)
		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;
			}
		}
	}
	for(int i = 0; i < nbArcs; i++) if(bad(i)) roads.erase(i); else if(good(i)) roads.insert(i);
}

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 7 ms 6264 KB correct
2 Correct 8 ms 6264 KB correct
3 Correct 8 ms 6448 KB correct
4 Correct 8 ms 6448 KB correct
5 Correct 7 ms 6448 KB correct
6 Correct 6 ms 6452 KB correct
7 Correct 6 ms 6564 KB correct
8 Correct 7 ms 6564 KB correct
9 Correct 6 ms 6564 KB correct
10 Correct 7 ms 6564 KB correct
11 Correct 6 ms 6564 KB correct
12 Correct 7 ms 6564 KB correct
13 Correct 7 ms 6564 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6264 KB correct
2 Correct 8 ms 6264 KB correct
3 Correct 8 ms 6448 KB correct
4 Correct 8 ms 6448 KB correct
5 Correct 7 ms 6448 KB correct
6 Correct 6 ms 6452 KB correct
7 Correct 6 ms 6564 KB correct
8 Correct 7 ms 6564 KB correct
9 Correct 6 ms 6564 KB correct
10 Correct 7 ms 6564 KB correct
11 Correct 6 ms 6564 KB correct
12 Correct 7 ms 6564 KB correct
13 Correct 7 ms 6564 KB correct
14 Correct 43 ms 7140 KB correct
15 Correct 43 ms 7140 KB correct
16 Correct 50 ms 7224 KB correct
17 Correct 37 ms 7224 KB correct
18 Correct 14 ms 7224 KB correct
19 Correct 36 ms 7224 KB correct
20 Correct 32 ms 7224 KB correct
21 Correct 37 ms 7224 KB correct
22 Correct 14 ms 7224 KB correct
23 Correct 17 ms 7224 KB correct
24 Correct 13 ms 7224 KB correct
25 Correct 8 ms 7224 KB correct
26 Correct 14 ms 7224 KB correct
27 Correct 13 ms 7224 KB correct
28 Correct 9 ms 7224 KB correct
29 Correct 8 ms 7224 KB correct
30 Correct 14 ms 7224 KB correct
31 Correct 13 ms 7224 KB correct
32 Correct 16 ms 7224 KB correct
33 Correct 13 ms 7224 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6264 KB correct
2 Correct 8 ms 6264 KB correct
3 Correct 8 ms 6448 KB correct
4 Correct 8 ms 6448 KB correct
5 Correct 7 ms 6448 KB correct
6 Correct 6 ms 6452 KB correct
7 Correct 6 ms 6564 KB correct
8 Correct 7 ms 6564 KB correct
9 Correct 6 ms 6564 KB correct
10 Correct 7 ms 6564 KB correct
11 Correct 6 ms 6564 KB correct
12 Correct 7 ms 6564 KB correct
13 Correct 7 ms 6564 KB correct
14 Correct 43 ms 7140 KB correct
15 Correct 43 ms 7140 KB correct
16 Correct 50 ms 7224 KB correct
17 Correct 37 ms 7224 KB correct
18 Correct 14 ms 7224 KB correct
19 Correct 36 ms 7224 KB correct
20 Correct 32 ms 7224 KB correct
21 Correct 37 ms 7224 KB correct
22 Correct 14 ms 7224 KB correct
23 Correct 17 ms 7224 KB correct
24 Correct 13 ms 7224 KB correct
25 Correct 8 ms 7224 KB correct
26 Correct 14 ms 7224 KB correct
27 Correct 13 ms 7224 KB correct
28 Correct 9 ms 7224 KB correct
29 Correct 8 ms 7224 KB correct
30 Correct 14 ms 7224 KB correct
31 Correct 13 ms 7224 KB correct
32 Correct 16 ms 7224 KB correct
33 Correct 13 ms 7224 KB correct
34 Execution timed out 3044 ms 33672 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 33672 KB correct
2 Correct 6 ms 33672 KB correct
3 Execution timed out 3038 ms 108024 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6264 KB correct
2 Correct 8 ms 6264 KB correct
3 Correct 8 ms 6448 KB correct
4 Correct 8 ms 6448 KB correct
5 Correct 7 ms 6448 KB correct
6 Correct 6 ms 6452 KB correct
7 Correct 6 ms 6564 KB correct
8 Correct 7 ms 6564 KB correct
9 Correct 6 ms 6564 KB correct
10 Correct 7 ms 6564 KB correct
11 Correct 6 ms 6564 KB correct
12 Correct 7 ms 6564 KB correct
13 Correct 7 ms 6564 KB correct
14 Correct 43 ms 7140 KB correct
15 Correct 43 ms 7140 KB correct
16 Correct 50 ms 7224 KB correct
17 Correct 37 ms 7224 KB correct
18 Correct 14 ms 7224 KB correct
19 Correct 36 ms 7224 KB correct
20 Correct 32 ms 7224 KB correct
21 Correct 37 ms 7224 KB correct
22 Correct 14 ms 7224 KB correct
23 Correct 17 ms 7224 KB correct
24 Correct 13 ms 7224 KB correct
25 Correct 8 ms 7224 KB correct
26 Correct 14 ms 7224 KB correct
27 Correct 13 ms 7224 KB correct
28 Correct 9 ms 7224 KB correct
29 Correct 8 ms 7224 KB correct
30 Correct 14 ms 7224 KB correct
31 Correct 13 ms 7224 KB correct
32 Correct 16 ms 7224 KB correct
33 Correct 13 ms 7224 KB correct
34 Execution timed out 3044 ms 33672 KB Time limit exceeded
35 Halted 0 ms 0 KB -