Submission #33223

#	Time	Username	Problem	Language	Result	Execution time	Memory
33223		model_code	Simurgh (IOI17_simurgh)	C++11	51 / 100	196 ms	22828 KiB

simurgh

/*
   	IOI 2017
	Problem: Finding Spanning Tree
	Author: PrinceOfPersia
	Subtask: 3
*/
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <string>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include "simurgh.h"
using namespace std;
#define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
#define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
#define rep(i, c) for(auto &(i) : (c))
#define x first
#define y second
#define pb push_back
#define PB pop_back()
#define iOS ios_base::sync_with_stdio(false)
#define sqr(a) (((a) * (a)))
#define all(a) a.begin() , a.end()
#define error(x) cerr << #x << " = " << (x) <<endl
#define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
#define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
#define coud(a,b) cout<<fixed << setprecision((b)) << (a)
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define umap unordered_map
#define double long double
typedef long long ll;
typedef pair<int,int>pii;
typedef vector<int> vi;
template <class T>  inline void smax(T &x,T y){ x = max((x), (y));}
template <class T>  inline void smin(T &x,T y){ x = min((x), (y));}
template <class T>	inline void sminmax(T &mn, T &mx, T x){smin(mn, x), smax(mx, x);}
const int maxn = 512, maxm = maxn * maxn / 2;
bool mark[maxn];
int h[maxn], ind[maxn][maxn], par[maxn], n, m, state[maxm], last_num[maxm];
int __edges[maxn];
vi __edges_vec;
vi adj[maxn];
pii edges[maxm];
bool bit[maxm];
int _next_ = 1;
int _last_id[maxm];
inline void _renew(){
	vi __edges_new;
	rep(i, __edges_vec)	if(bit[i] && _last_id[i] != _next_)
		__edges_new.pb(i), _last_id[i] = _next_;
	++ _next_;
	__edges_vec = __edges_new;
}
vi __ans;
inline int query(){
	_renew();
	int res = count_common_roads(__edges_vec);
	if(res == n-1)
		__ans = __edges_vec;
	return res;
}
inline void toggle(int i){
	if(!bit[i]){
		bit[i] = true;
		__edges_vec.pb(i);
	}
	else
		bit[i] = false;
}
inline void reset(){
	while(!__edges_vec.empty()){
		int e = __edges_vec.back();
		__edges_vec.PB;
		bit[e] = false;
	}
}
vi back_edges[maxn];
inline void dfs(int v = 0, int p = -1){
	if(~p)	h[v] = h[p] + 1;
	mark[v] = true;
	par[v] = p;
	rep(u, adj[v])
		if(!mark[u])
			dfs(u, v);
	if(~p)
		toggle(ind[v][p]);
}
int tree_score;
inline void DFS(int v = 0){
	rep(u, adj[v]){
		if(v == par[u])
			DFS(u);
		else if(u != par[v] && h[u] < h[v]){
			int e = ind[v][u];
			int cur = v;
			while(cur != u){
				back_edges[cur].pb(e);
				cur = par[cur];
			}
		}
	}
	if(~par[v]){
		int e2p = ind[v][par[v]];
		int for_a_one = -1, mn = tree_score, mx = mn;
		last_num[e2p] = tree_score;
		toggle(e2p);
		rep(e, back_edges[v]){
			if(min(for_a_one, state[e]) == -1){
				toggle(e);
				last_num[e] = query();
				if(~state[e])
					for_a_one = last_num[e] + (!state[e]);
				sminmax(mn, mx, last_num[e]);
				toggle(e);
			}
		}
		toggle(e2p);
		smax(mx, for_a_one);
		state[e2p] = tree_score == mx;
		rep(e, back_edges[v])	if(state[e] == -1)
			state[e] = last_num[e] == mx;
	}
	
}
vi find_roads(int n, vi v, vi u){
	::n = n;
	m = v.size();
	memset(ind, -1, sizeof ind);
	memset(state, -1, sizeof state);
	For(i,0,m){
		edges[i] = {v[i], u[i]};
		ind[v[i]][u[i]] = ind[u[i]][v[i]] = i;
		adj[v[i]].pb(u[i]), adj[u[i]].pb(v[i]);
	}
	dfs();
	tree_score = query();
	DFS();
	reset();
	For(i,0,m)	if(state[i] == 1)
		toggle(i);
	query();
	return __ans;
}

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