Submission #73499

#	Time	Username	Problem	Language	Result	Execution time	Memory
73499		SmsS	Simurgh (IOI17_simurgh)	C++14	0 / 100	4 ms	636 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;
//	cout << root << endl;
	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]);
//			cout << root << ' ' << i << endl;
			dfs(i);
		}else if(sc && h[i] > h[root]+1){
//			cout << i << ' ' << root << endl;
			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;
			}
//			cout << s[adj[i][root]] << ' ' << root << ' ' << i << endl;
			if(!s[adj[i][root]]){
				int mx = 0;
				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());
					res[t] = adj[x][y];
					x = y;
				}
				int cnt = 0;
				x = i;
				while(x != root){
					int y = par[x];
					if(c[cnt] != mx){
						s[adj[x][y]] = 2;
					}else s[adj[x][y]] = 1;
					cnt++;
					x = y;
				}
				if(cur != mx){
					s[adj[root][i]] = 2;
				}else s[adj[root][i]] = 1;
			}
		}
	}
}

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;
	par[0] = -1;
	dfs(0);
	cur = count_common_roads(res);
	sc = 1;
	fill(seen,seen+n,0);
	dfs(0);
//	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 res;
}

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