Submission #435477

#	Time	Username	Problem	Language	Result	Execution time	Memory
435477		Bill_00	Keys (IOI21_keys)	C++17	37 / 100	2555 ms	42876 KiB

keys

#include <vector>
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> >adj[300000];
vector<int>got[300000];
int key[300000],room[300000],r[300000],p[300000];
void dfs(int node){
	room[node]=1;
	if(key[r[node]]==0){
		key[r[node]]=1;
		for(int t:got[r[node]]){
			if(room[t]==0) dfs(t);
		}
	}
	vector<int>y;
	for(pair<int,int>to:adj[node]){
		int next=to.first;
		int color=to.second;
		if(room[next]) continue;
		if(key[color]){
			y.push_back(next);
		}
		else{
			got[color].push_back(next);
		}
	}
	for(int i:y) dfs(i);
}
vector<int> find_reachable(vector<int> R,vector<int> u,vector<int> v,vector<int> c) {
	vector<int>ans;
	int n=R.size(),m=u.size(),mn=1e9;
	ans.resize(n);
	for(int i=0;i<m;i++){
		adj[u[i]].push_back({v[i],c[i]});
		adj[v[i]].push_back({u[i],c[i]});
	}
	for(int i=0;i<n;i++){
		r[i]=R[i];
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			key[j]=0;
			room[j]=0;
			got[j].clear();
		}
		dfs(i);
		for(int j=0;j<n;j++){
			if(room[j]==1) p[i]++;
		}
	}
	for(int i=0;i<n;i++){
		mn=min(mn,p[i]);
	}
	for(int i=0;i<n;i++){
		if(mn==p[i]) ans[i]=1;
	}
	return ans;
}

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