Submission #813935

#	Time	Username	Problem	Language	Result	Execution time	Memory
813935		alvingogo	Keys (IOI21_keys)	C++17	37 / 100	3068 ms	88748 KiB

keys

#include <vector>
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n=r.size();
	vector<vector<pair<int,int> > > e(n);
	int m=u.size();
	for(int i=0;i<m;i++){
		e[u[i]].push_back({v[i],c[i]});
		e[v[i]].push_back({u[i],c[i]});
	}
	vector<int> val(n),ans(n);
	for(int i=0;i<n;i++){
		queue<int> q;
		vector<int> vis(n),vz(n);
		vector<queue<int> > to(n);
		q.push(i);
		vz[i]=1;
		while(q.size()){
			auto h=q.front();
			q.pop();
			val[i]++;
			for(auto y:e[h]){
				if(vz[y.fs]){
					continue;
				}
				if(vis[y.sc]){
					q.push(y.fs);
					vz[y.fs]=1;
				}
				else{
					to[y.sc].push(y.fs);
				}
			}
			if(!vis[r[h]]){
				vis[r[h]]=1;
				while(to[r[h]].size()){
					auto u=to[r[h]].front();
					to[r[h]].pop();
					if(vz[u]){
						continue;
					}
					vz[u]=1;
					q.push(u);
				}
			}
		}
	}
	int mn=1e9;
	for(int i=0;i<n;i++){
		mn=min(mn,val[i]);
	}
	for(int i=0;i<n;i++){
		if(val[i]==mn){
			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