Submission #1140948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140948		urosk	Simurgh (IOI17_simurgh)	C++20	0 / 100	3109 ms	163300 KiB

simurgh

#include "simurgh.h"
#include "bits/stdc++.h"
#define dbg(X) cerr<<#X<<": "<<X<<endl;
#define here cerr<<"===============================\n"
#define pb push_back
#define fi first
#define sc second
#define si(a) (ll)(a.size())
using namespace std;

using ll = int;
using pll = pair<ll,ll>;
const ll maxn = 505;
ll n,m;
vector<ll> g[maxn];
array<ll,3> e[maxn];
ll in[maxn],ti = 0;
ll mn[maxn];
bool vis[maxn];
vector<ll> v;
ll tu[maxn];
ll par[maxn];
ll out[maxn];
bool intree(ll x,ll y){return in[x]<=in[y]&&out[x]>=out[y];}
void dfs(ll u,ll p) {
	in[u] = ++ti;
	vis[u] = 1;
	mn[u] = in[u];
	for(ll j : g[u]) {
		ll s = e[j][0]^e[j][1]^u;
		if(s==p) continue;
		if(vis[s]) {
			mn[u] = min(mn[u],mn[s]);
		}else {
			dfs(s,u);
			mn[u] = min(mn[u],mn[s]);
			v.pb(j);
			par[s] = j;
			if(mn[s]>=in[s]) tu[j] = 1;
		}
	}
	out[u] = ti;
}
vector<ll> f(ll i,ll j) {
	vector<ll> w;
	for(ll x : v) if(x!=i) w.pb(x);
	w.pb(j);
	return w;
}
ll ask(vector<ll> v) {
	vector<ll> w;
	for(ll x : v) w.pb(x-1);
	if(si(v)!=n-1) {
		dbg(si(v));
		cerr<<"losee"<<endl;
		exit(0);
	}
	return count_common_roads(w);
}
vector<ll> cur;
ll dsu[maxn];
ll root(ll x) {
	while(x!=dsu[x]) {
		dsu[x] = dsu[dsu[x]];
		x = dsu[x];
	}
	return x;
}
bool upd(ll x,ll y) {
	x = root(x),y = root(y);
	if(x==y) return 0;
	dsu[x] = y;
	return 1;
}
ll poc = 0;
void dodaj() {
	iota(dsu+1,dsu+1+n,1);
	for(ll i : cur) {
		upd(e[i][0],e[i][1]);
	}
	poc = 0;
	for(ll i : v) {
		if(upd(e[i][0],e[i][1])) cur.pb(i),poc+=tu[i];
	}
}
std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> V) {
	n = N;
	m = si(u);
	for(ll j = 0;j<m;j++) {
		ll x = u[j]+1,y = V[j]+1;
		g[x].pb(j+1);
		g[y].pb(j+1);
		e[j+1] = {x,y,j+1};
	}
	for(ll i = 1;i<=m;i++) tu[i] = -1;
	dfs(1,1);
	ll c = ask(v);
	for(ll i : v) {
		if(tu[i]==1||tu[i]==0) continue;
		ll u = e[i][0],s = e[i][1];
		if(in[u]>in[s]) swap(u,s);
		ll k = -1;
		for(ll j = 1;j<=m;j++) {
			if(j==i) continue;
			ll x = e[j][0],y = e[j][1];
			if(in[x]>in[y]) swap(x,y);
			if(!intree(x,y)) continue;
			if(intree(x,u)&&intree(s,y)) {
				k = j;
				break;
			}
		}
		ll x = e[k][0],y = e[k][1];
		if(in[x]>in[y]) swap(x,y);
		vector<ll> nw = f(i,k);
		ll c2 = ask(nw);
		vector<pll> tr;
		tr.pb({c2,i});
		bool imalos = 0;
		ll mn = -1,mx = -1;
		while(y!=x) {
			ll j = par[y];
			if(tu[j]!=-1) {
				if(tu[j]==0) {
					nw = f(j,k);
					if(mx==-1) mx = ask(nw);
				}else if(tu[j]==1) {
					nw = f(j,k);
					if(mn==-1) mn = ask(nw);
				}
				y = e[j][0]^e[j][1]^y;
				continue;
			}
			nw = f(j,k);
			tr.pb({ask(nw),j});
			y = e[j][0]^e[j][1]^y;
		}
		sort(tr.begin(),tr.end());
		if(mx!=-1) {
			for(pll p : tr) {
				if(p.fi==mx) tu[p.sc] = 0;
				else tu[p.sc] = 1;
			}
		}else if(mn!=-1) {
			for(pll p : tr) {
				if(p.fi==mx) tu[p.sc] = 0;
				else tu[p.sc] = 1;
			}
		}else {
			mn = tr[0].fi,mx = tr.back().fi;
			for(pll p : tr) {
				if(p.fi==mx) tu[p.sc] = 0;
				else tu[p.sc] = 1;
			}
		}
	}
	for(ll i = 1;i<=n;i++) {
		cur.clear();
		for(ll j : g[i]) cur.pb(j);
		dodaj();
		ll f = ask(cur)-poc;
		ll last = 0;
		for(ll j = 0;j<f;j++) {
			ll tl = last,tr = si(g[i])-1,mid,rez = -1;
			while(tl<=tr) {
				mid = (tl+tr)/2;
				cur.clear();
				for(ll d = 0;d<=mid;d++) cur.pb(g[i][d]);
				dodaj();
				ll cnt = ask(cur)-poc;
				if(cnt>j) rez = mid,tr = mid-1;
				else tl = mid+1;
			}
			if(rez==-1) while(1) here;
			tu[g[i][rez]] = 1;
			last = rez+1;
		}
	}
	vector<ll> ans;
	for(ll i = 1;i<=m;i++) if(tu[i]==1) ans.pb(i-1);
	//cerr<<si(ans)<<endl;
	//cerr<<"ans: "<<endl;
	//for(ll x : ans) cerr<<x<< " ";
	//cerr<<endl;
	return ans;
}

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