Submission #73513

#	Time	Username	Problem	Language	Result	Execution time	Memory
73513		SmsS	Simurgh (IOI17_simurgh)	C++14	0 / 100	3 ms	616 KiB

simurgh

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
#define for2(a,b,c) for(int a = b; a < c; a++)
#include "simurgh.h"

const int maxn = 510;
int adj[maxn][maxn];
bool seen[maxn];
bool burn[maxn];
int s[maxn*maxn/2];
int h[maxn];
int par[maxn];
vector<int> res;
bool sc = 0;
int cur;
int n;

void dfs(int root){
	seen[root] = 1;
	for2(i,0,n) if(adj[i][root] != -1){
		if(!seen[i]){
			h[i] = h[root]+1;
			par[i] = root;
			if(!sc)res.pb(adj[i][root]);
			dfs(i);
		}else if(sc && h[i] > h[root]+1){
			int x = i;
			while(x != root){
				int y = par[x];
				if(s[adj[x][y]]){
					int t = 0;
					for2(i,0,n-1) if(res[i] == adj[x][y]) t = i;
					res[t] = adj[i][root];
					if(count_common_roads(res) == cur-(s[adj[x][y]]==2)) s[adj[i][root]] = 1;
					else s[adj[i][root]] = 2;
					res[t] = adj[x][y];
					break;
				}
				x = y;
			}
			if(!s[adj[i][root]]){
				int mx = cur;
				int mn = cur;
				vector<int> c;
				x = i;
				while(x != root){
					int y = par[x];
					int t = 0;
					for2(i,0,n-1) if(res[i] == adj[x][y]) t = i;
					res[t] = adj[i][root];

					c.pb(count_common_roads(res));
					mx = max(mx,c.back());
					mn = min(mn,c.back());
					res[t] = adj[x][y];
					x = y;
				}
				int cnt = 0;
				x = i;
				while(x != root){
					int y = par[x];
//					cout << x << ' ' << y << endl;
					if(c[cnt] != mx && mx != mn){
						s[adj[x][y]] = 2;
					}else s[adj[x][y]] = 1;
					cnt++;
					x = y;
				}
				if(cur != mx && mx != mn){
					s[adj[root][i]] = 2;
				}else s[adj[root][i]] = 1;
	//			for2(i,0,8) cout << s[i] << endl;
			}
		}
	}
}

//int par[maxn];
int getpar(int x){
	if(par[x] < 0) return x;
	return par[x] = getpar(par[x]);
}

std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
	int m = u.size();
	n = N;
	for2(i,0,n) for2(j,0,n) adj[i][j] = -1;
	for2(i,0,m) adj[u[i]][v[i]] = adj[v[i]][u[i]] = i;
	dfs(0);
	cur = count_common_roads(res);
	sc = 1;
	fill(seen,seen+n,0);
	dfs(0);

	fill(par,par+n,-1);
	vector<int> ans;
	for2(i,0,m) if(s[i] == 2){
		ans.pb(i);
		int x = getpar(v[i]);
		int y = getpar(u[i]);
		if(x == y) continue;
		par[x] = y;
	}
	for(auto e : res){
		int x = getpar(v[e]);
		int y = getpar(u[e]);
		if(x == y) continue;
		par[x] = y;
		res.pb(e);
	}
//	for2(i,0,m) cout << s[i] << endl;
	//for2(i,0,m) if(!s[i]) s[i] = 2;
	
	res.clear();
	for2(i,0,m) if(s[i] == 2) res.pb(i);
	return ans;
}

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