Submission #827932

#	Time	Username	Problem	Language	Result	Execution time	Memory
827932		Liudas	Keys (IOI21_keys)	C++17	100 / 100	1473 ms	138752 KiB

keys

#include<bits/stdc++.h>
#include "keys.h"
using namespace std;
typedef long long ll;
struct E{
	int fr,to,val;
};
int n,m,bel[300005],low[300005],dfn[300005],ins[300005],sign,st[300005],top,SCC;
int a[300005],oud[300005],fa[300005],ind[300005],vst[300005],clx[300005];
vector<int> g[300005];
vector<E> G[300005];
bool T;
bool operator <(E x,E y){return x.val!=y.val?x.val<y.val:x.to!=y.to?x.to<y.to:x.fr<y.fr;}
void dfs(int x){
	st[++top]=x,low[x]=dfn[x]=++sign,ins[x]=1;
	for(int y:g[x]){
		if(!dfn[y])dfs(y),low[x]=min(low[x],low[y]);
		else if(ins[y])low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x]){
		int tmp=0;
		SCC++;
		while(tmp!=x)bel[tmp=st[top--]]=SCC,ins[tmp]=0,ind[SCC]++;
	}
}
vector<E> edge[300005];
bool key[300005];
int clk[300005],cle[300005],iscle[300005];
queue<int> q;
int gf(int x){
	return fa[x]==x?x:fa[x]=gf(fa[x]);
}
struct W{
	int x,y;
}t[10000005];
int cnt=0;
void Inskey(int x){
	if(key[x])return ;
	key[x]=1,clk[++clk[0]]=x;
	//cout<<"Ins:"<<x<<'\n';
	while(edge[x].size()&&!T){
		E it=edge[x].back();
		if(!vst[it.to]){
			q.push(it.to);
			if(gf(it.fr)!=gf(it.to))T=1;
			else vst[it.to]=1,clx[++clx[0]]=it.to;
		}
		t[++cnt]={it.fr,it.to};
		edge[x].pop_back();
	}
}
void InsEdge(E x){
	//cout<<x.val<<' '<<key.count(x.val)<<'\n';
	if(key[x.val]){
		if(!vst[x.to]){
			q.push(x.to);
			if(gf(x.fr)!=gf(x.to))T=1;
			else vst[x.to]=1,clx[++clx[0]]=x.to;
		}
		t[++cnt]={x.fr,x.to};
	}
	else {
		if(!iscle[x.val])iscle[x.val]=1,cle[++cle[0]]=x.val;
		edge[x.val].push_back(x);
	}
}
void bfs(int x){
	//cout<<"AA:"<<key.size()<<' '<<key.count(0)<<'\n';
	q.push(x),vst[x]=1,clx[++clx[0]]=x;//,cout<<i<<'\n';
	while(!q.empty()){
		int x=q.front();
		q.pop(),Inskey(a[x]);
		if(T){
			while(!q.empty())q.pop();
			break;
		}
		for(E i:G[x]){
			InsEdge(i);
			if(T)break;
		}
		if(T){
			while(!q.empty())q.pop();
		}
	}
	//puts("PP");
	while(clk[0])key[clk[clk[0]--]]=0;
	while(clx[0])vst[clx[clx[0]--]]=0;
	while(cle[0])iscle[cle[cle[0]]]=0,edge[cle[cle[0]--]].clear();
}
vector<int> find_reachable(vector<int> R,vector<int> U,vector<int> V,vector<int> C){
	n=R.size(),m=U.size();
	for(int i=1;i<=n;i++)a[i]=R[i-1],fa[i]=i;
	for(int i=1,x,y,z;i<=m;i++){
		x=U[i-1],y=V[i-1],z=C[i-1];
		x++,y++;
		G[x].push_back({x,y,z}),G[y].push_back({y,x,z});
	}
	int nfl=0;
	while(1){
		bool fl=0;
		for(int i=1;i<=n;i++)if(gf(i)==i)T=0,bfs(i),fl|=T;
		for(int i=1;i<=cnt;i++)fa[gf(t[i].x)]=gf(t[i].y),g[t[i].x].push_back(t[i].y);
		cnt=0;
		if(!fl){
			nfl++;
			if(nfl==2)break;
		}
	}
	for(int i=1;i<=n;i++)
		sort(g[i].begin(),g[i].end()),g[i].resize(unique(g[i].begin(),g[i].end())-g[i].begin());
	for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
	for(int i=1;i<=n;i++)for(int j:g[i])if(bel[i]!=bel[j])oud[bel[i]]++;
	int mn=1e9;
	for(int i=1;i<=SCC;i++)if(!oud[i])mn=min(mn,ind[i]);
	cerr<<mn<<'\n';
	vector<int> ans(n);
	for(int i=1;i<=n;i++)if(!oud[bel[i]]&&ind[bel[i]]==mn)ans[i-1]=1;
	return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 33 / 33