답안 #52072 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52072	2018-06-23T16:07:46 Z	ernestvw	Simurgh (IOI17_simurgh)	C++11	30 / 100	3000 ms	108024 KB

simurgh

/*
	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #52072

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0