Submission #349421

#	Time	Username	Problem	Language	Result	Execution time	Memory
349421		ryansee	Simurgh (IOI17_simurgh)	C++14	100 / 100	258 ms	6252 KiB

simurgh

#include "simurgh.h"

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

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=long long; 
using ld=long double;
#define FOR(i,s,e) for(int i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

long long LLINF = 1e18;
int INF = 1e9+1e6;
#define MAXN (506)
vector<int> r, tmp;
int m, p[MAXN], state[MAXN*MAXN], depth[MAXN], pe[MAXN];
struct u {
	int p[MAXN], sz[MAXN];
	void init() {
		FOR(i,0,MAXN-1) p[i]=i,sz[i]=1;
	}
	bool merge(int x,int y) {
		x=find(x), y=find(y);
		if(x==y) return 0;
		if(sz[x]>sz[y]) swap(x, y);
		p[x]=y, sz[y]+=sz[x]; return 1;
	}
	int find(int x) { return (p[x] == x) ? x : p[x] = find(p[x]); }
} u;

struct edge {
	int x, ind;
}; vector<edge> v[MAXN];
bitset<MAXN*MAXN> span;
bitset<MAXN> vis;

int ask(vector<int> r) {
	return count_common_roads(r);
}

vector<int> find_roads(int n, vector<int> U, vector<int> V) {
	m = siz(U);
	FOR(i,0,m-1) {
		int a=U[i], b=V[i];
		v[a].pb({b, i}), v[b].pb({a, i});
	}
	function<void(ll)>dfs=[&](ll x){
		vis[x]=1;
		for(auto i:v[x]) if(!vis[i.x]) {
			depth[i.x]=depth[x]+1, p[i.x] = x, pe[i.x]=i.ind, dfs(i.x), span[i.ind] = 1, tmp.eb(i.ind);
		}
	};
	dfs(0), assert(tmp.size() == n-1);
	
	int init = ask(tmp);
	FOR(i,0,m-1) if(!span[i]) {
		int a=U[i], b=V[i];
		if(depth[a] > depth[b]) swap(a, b);
		
		vector<int> E;
		int done = -1;
		while(b ^ a) {
			if(state[pe[b]]) done=pe[b];
			else E.eb(pe[b]);
			b = p[b];
		}
		if(E.empty()) continue;
		
		if(done == -1) {
			vector<pi> ind;
			for(auto e:E) {
				tmp.erase(find(all(tmp), e)), tmp.eb(i);
				ind.eb(ask(tmp), e);
				tmp.pop_back(), tmp.eb(e);
			}
			sort(all(ind));
			if(ind[0].f == ind.back().f) {
				for(auto i:ind) state[i.s] = init == i.f ? 1 : 2;
			} else {
				for(auto i:ind) if(i.f == ind.back().f) state[i.s] = 1; else state[i.s] = 2;
			}
		} else {
			tmp.erase(find(all(tmp), done)), tmp.eb(i);
			int init = ask(tmp);
			tmp.pop_back(), tmp.eb(done);
			
			for(auto e:E) {
				tmp.erase(find(all(tmp), e)), tmp.eb(i);
				if(ask(tmp) == init) state[e] = state[done];
				else state[e] = 3 - state[done];
				tmp.pop_back(), tmp.eb(e);
			}
		}
	}
	
	FOR(i,0,m-1) if(span[i] && state[i]==0) state[i] = 2; else if(!span[i]) assert(state[i] == 0);
	
	// FOR(i,0,m-1) if(span[i]) {
		// cerr<<i<<" is "<<state[i]<<'\n';
	// }
	
	FOR(i,0,n-1) {
		deque<int> E;
		for(auto j:v[i]) if(!span[j.ind] && !state[j.ind]) E.eb(j.ind);
		if(E.empty()) continue;
		
		shuffle(all(E), rng);
		auto good=[&](ll until) {
			vector<int> tmp2;
			u.init();
			FOR(ii,0,until) { int i=E[ii];
				u.merge(U[i], V[i]);
				tmp2.eb(i);
			}
			
			int cost = 0;
			for(auto i:tmp) if(u.merge(U[i], V[i])) {
				tmp2.eb(i), cost += state[i] == 2;
			}
			
			return ask(tmp2) - cost;
		};
		
		int have = good(siz(E) - 1);
		
		for(;have;--have) {
			assert(siz(E));
			int st=-1, en=siz(E)-1;
			while(en-st>1) {
				int mid=(st+en)>>1;
				if(good(mid)>=1) en=mid;
				else st=mid;
			}
			FOR(j,0,en-1) state[E.front()]=1, E.pop_front();
			state[E.front()]=2, E.pop_front();				
		}
		
		while(E.size()) state[E.front()]=1, E.pop_front();
	}
	
	assert(r.empty());
	FOR(i,0,m-1) if(state[i]==2) r.eb(i);
	assert(siz(r)==n-1);
	
	return r;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from simurgh.cpp:3:
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:69:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |  dfs(0), assert(tmp.size() == n-1);
      |                 ~~~~~~~~~~~^~~~~~

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