Submission #137481

#	Time	Username	Problem	Language	Result	Execution time	Memory
137481		Utaha	Parachute rings (IOI12_rings)	C++14	0 / 100	995 ms	65120 KiB

rings

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define EL cout<<'\n'
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
	REP(i,SZ(V)) out<<V[i]<<((i!=SZ(V)-1)?" ":"");
	return out;
}
#define version 20190726
//}}}
const ll maxn=1000005;
const ll maxlg=20;
const ll INF64=1e18;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return res;
}

int n;
int dsu[maxn],sz[maxn];
vector<int> ring;
int notst=0;
int deg[maxn];
vector<int> v;
bool vis[maxn];

vector<int> edge[maxn];

int find(int u){
	if(dsu[u]==u) return u;
	return dsu[u]=find(dsu[u]);
}
void mrg(int u,int v){
	u=find(u);
	v=find(v);
	if(u==v) return;
	if(sz[u]<sz[v]) swap(u,v);
	dsu[v]=u;
	sz[u]+=sz[v];
}

void Init(int N_) {
	n = N_;
	REP(i,n) dsu[i]=i,sz[i]=1;
	REP(i,n) ring.pb(i);
	v=ring;
}

vector<int> path;
vector<int> _r;
void dfs(int u,int par){
	// cout<<u<<' '<<par<<'\n';
	vis[u]=1;
	path.pb(u);
	for(int v:edge[u]) if(v!=par){
		if(vis[v]){
			if(SZ(_r)!=0) continue;
			for(int i=SZ(path)-1;i>=0;i--){
				_r.pb(path[i]);
				if(path[i]==v) break;
			}
		}
		else{
			dfs(v,u);
		}
	}
	path.pop_back();
}

void Link(int A, int B) {
	deg[A]++;
	deg[B]++;
	edge[A].pb(B);
	edge[B].pb(A);
	if(find(A)==find(B)){
		notst++;
		if(notst==1){
			REP(i,n) if(!vis[i]) dfs(i,-1);
			ring=_r;
			sort(ALL(ring));
		}
	}
	else{
		mrg(A,B);
	}
	// cout<<"???: "<<A<<' '<<B<<'\n';
	if(deg[A]>3||deg[B]>3){
		notst=880301;
	}
	if(deg[A]==3){
		vector<int> nw;
		for(int i:v){
			bool f=(i==A);
			for(int j:edge[A]) if(j==i) f=1;
			if(f) nw.pb(i);
		}
		sort(ALL(nw));
		v=nw;
	}
	if(deg[B]==3){
		vector<int> nw;
		for(int i:v){
			bool f=(i==B);
			for(int j:edge[B]) if(j==i) f=1;
			if(f) nw.pb(i);
		}
		sort(ALL(nw));
		v=nw;
	}
}

int CountCritical() {
	// cout<<"Info: "<<notst<<' '<<SZ(v)<<' '<<SZ(ring)<<'\n';
	if(notst>=2){
		return 0;
	}
	if(SZ(v)==n) return SZ(ring);
	int ans=0;
	for(int i:v){
		int l=0,r=SZ(ring);
		while(l<r-1){
			int mid=(l+r)/2;
			if(ring[mid]<=i) l=mid;
			else r=mid;
		}
		ans+=ring[l]==i;
	}
	return ans;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31