Submission #435499

#	Time	Username	Problem	Language	Result	Execution time	Memory
435499		kshitij_sodani	Keys (IOI21_keys)	C++17	37 / 100	2568 ms	34752 KiB

keys

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;

#include <vector>

int val[300001];
int vis[300001];
int vis2[300001];

vector<pair<int,int>> adj[300001];
/*int par[300001];
int ss[300001];
int find(int no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
*/
//queue<int> ss;
std::vector<int> find_reachable(std::vector<int> it, std::vector<int> uu, std::vector<int> vv, std::vector<int> cc) {
	int n=it.size();
	int m=uu.size();
	//std::vector<int> ans(r.size(), 1);
	/*for(int i=0;i<n;i++){
		par[i]=i;
		ss[i]=1;
	}*/

	for(int i=0;i<m;i++){
		/*int x=find(uu[i]);
		int y=find(vv[i]);
		if(x!=y){
			ss[y]+=ss[x];
		}
		par[x]=y;*/
		adj[uu[i]].pb({vv[i],cc[i]});
		adj[vv[i]].pb({uu[i],cc[i]});

		//continue;
		
	}
	vector<int> ans;
	for(int i=0;i<n;i++){
		ans.pb(0);
	}
	int st=0;
	for(int i=0;i<n;i++){
		int co=0;
		for(auto j:adj[i]){
			if(j.b==it[i]){
				co++;
			}
		}
		if(co==0){
			st=1;
			ans[i]=1;
		}
	}
	if(st){
		return ans;
	}

	vector<pair<int,int>> tt;
	for(int ii=0;ii<n;ii++){
		//tt.pb({ss[find(i)],i});
		val[ii]=0;
		queue<int> ss;
		//ss.clear();
		map<int,vector<int>> cur;

		for(int j=0;j<n;j++){
			vis[j]=0;
			vis2[j]=0;
		}
		ss.push(ii);
		vis[ii]=1;
		//vis2[it[ii]]=1;
		//int pp;
		//add(ii);
		/*for(auto j:adj[0]){

		}*/

		while(ss.size()){
			int no=ss.front();
			ss.pop();
			if(vis2[it[no]]==0){
				for(auto j:cur[it[no]]){
					if(vis[j]==0){
						vis[j]=1;
						ss.push(j);
					}
				}
				cur[it[no]].clear();
			}
			vis2[it[no]]=1;
			for(auto j:adj[no]){
				if(vis[j.a]==0){
					if(vis2[j.b]==1){
						ss.push(j.a);
						vis[j.a]=1;
						continue;
					}
					else{
						cur[j.b].pb(j.a);
					}
				}
			}

		}
		for(int i=0;i<n;i++){
			val[ii]+=vis[i];
		}
		/*while(true){
			int st=-1;
			for(int i=0;i<n;i++){
				if(vis[i]==1){
					for(auto j:adj[i]){
						if(vis[j.a]==0 and vis2[j.b]==1){
							st=j.a;
						}
					}
				}
			}
			if(st>=0){
				val[ii]++;
				vis[st]=1;
				vis2[it[st]]=1;
			}
			else{
				break;
			}

		}*/
		/*ss.push(i);
		while(ss.size()){
			int no=ss.front();
			val[no]++;
			vis2[]
			for(auto j)
		}
*/
		tt.pb({val[ii],ii});
	}
	sort(tt.begin(),tt.end());
	for(int i=0;i<n;i++){
		if(tt[i].a==tt[0].a){
			ans[tt[i].b]=1;
		}
	}
	return ans;
}

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