Submission #1043329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043329		amirhoseinfar1385	Keys (IOI21_keys)	C++17	9 / 100	96 ms	53376 KiB

keys

#include <vector>
#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+10;
vector<int>revadj[maxn],adj[maxn],allc[maxn],adjs[maxn];
int all[maxn],vis2[maxn],vis[maxn],n,m,par[maxn],nago[maxn];
vector<int>res;
deque<int>allv;

void dfs(int u){
	vis[u]=1;
	for(auto x:adj[u]){
		if(vis[x]==0){
			dfs(x);
		}
	}
	allv.push_front(u);
}

void sfd(int u,int had){
	vis2[u]=1;
	allc[had].push_back(u);
	par[u]=had;
	for(auto x:revadj[u]){
		if(vis2[x]==0){
			sfd(x,had);
		}
	}
}

void calcscc(){
	for(int i=0;i<n;i++){
		if(vis[i]==0){
			dfs(i);
		}
	}
	while((int)allv.size()>0){
		if(vis2[allv.front()]==0){
			sfd(allv.front(),allv.front());
		//	cout<<"hey: "<<allv.front()<<endl;
		//	for(auto x:allc[allv.front()]){
		//		cout<<x<<" ";
		//	}
		//	cout<<endl;
		}
		allv.pop_front();
	}
}

void calres(){
	for(int i=0;i<n;i++){
		for(auto x:adj[i]){
			if(par[i]!=par[x]){
				nago[par[i]]=1;
			}
		}
	}
	int mainres=n+1;
	for(int i=0;i<n;i++){
		if(par[i]==i&&nago[i]==0){
			mainres=min(mainres,(int)allc[i].size());
		}
	}
	for(int i=0;i<n;i++){
		if((int)allc[i].size()==mainres&&par[i]==i&&nago[i]==0){
			for(auto x:allc[i]){
				res[x]=1;
			}
		}	
	}
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	n=(int)r.size();
	m=(int)u.size();
	res.resize(n);
	for(int i=0;i<n;i++){
		all[i]=r[i];
	}
	for(int i=0;i<m;i++){
		if(all[u[i]]==c[i]){
			adj[u[i]].push_back(v[i]);
			revadj[v[i]].push_back(u[i]);
		}
		if(all[v[i]]==c[i]){
			adj[v[i]].push_back(u[i]);
			revadj[u[i]].push_back(v[i]);
		}
	}
	calcscc();
	calres();
	for(int i=0;i<n;i++){
		if(all[i]!=0&&res[i]==0){
			exit(23);
		}
	}
	return res;
}

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