Submission #69929

#	Time	Username	Problem	Language	Result	Execution time	Memory
69929		top34051	Simurgh (IOI17_simurgh)	C++17	51 / 100	260 ms	6580 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 500 + 5;
const int maxm = 250000 + 5;

int n,m;

pii e[maxm];
int head[maxn];
int act[maxm], pos[maxm];
vector<int> tree;

vector<pii> way[maxn];
int par[maxn], come[maxn];

vector<int> path;
int rec[maxm];

int res[maxm];

int ask(int last, int id) {
    if(last==-1 || id==-1 || res[last]==-1 || res[id]==-1) {
        return count_common_roads(tree);
    }
    return rec[last] + res[last] - res[id];
}

int findhead(int x) {
	if(x==head[x]) return x;
	return head[x] = findhead(head[x]);
}

void dfs(int u, int last, int id) {
	par[u] = last; come[u] = id;
	for(auto t : way[u]) {
		int v = t.X, tid = t.Y;
		if(v==last) continue;
		dfs(v,u,tid);
	}
}

void prep(int x, int y) {
	dfs(x,-1,0);
	path.clear();
	for(int i=y;i!=x;i=par[i]) {
//		printf("%d %d : %d\n",par[i],i,come[i]);
		path.push_back(come[i]);
	}
}

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
	n = N; m = U.size();
	for(int i=0;i<n;i++) head[i] = i;
	for(int i=0;i<m;i++) {
		int u = U[i], v = V[i];
		e[i] = {u,v};
		pos[i] = -1;
		if(findhead(u)!=findhead(v)) {
			head[findhead(u)] = findhead(v);
			pos[i] = tree.size();
			tree.push_back(i);
			way[u].push_back({v,i});
			way[v].push_back({u,i});
		}
        res[i] = -1;
	}

	int ori = ask(-1,-1);
//	printf("ori = %d\n",ori);

	for(int i=0;i<m;i++) {
		if(pos[i]!=-1) continue;
		int u = e[i].X, v = e[i].Y;
		prep(u,v);
		int last = -1;
//		printf("edge %d\n",i);
		for(auto id : path) {
			tree[pos[id]] = i;
			rec[id] = ask(last,id);
//			printf("\trec %d = %d\n",id,rec[id]);
			tree[pos[id]] = id;
			last = id;
		}

		res[i] = 0;
		for(auto id : path) {
			if(rec[id]-ori == 1) res[i] = 1;
		}
//		printf("\t\tres = %d\n",res[i]);

		for(auto id : path) {
            res[id] = ori + res[i] - rec[id];
//            printf("\t\tres %d = %d\n",id,res[id]);
		}
	}

	vector<int> vec;
	for(int i=0;i<m;i++) if(res[i]) vec.push_back(i);
//	for(auto t : vec) printf("%d ",t);
	return vec;
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30