Submission #1044478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044478		Unforgettablepl	Keys (IOI21_keys)	C++17	37 / 100	3017 ms	26168 KiB

keys

#include <bits/stdc++.h>
using namespace std;

vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c){
	int n = r.size();
	int m = u.size();
	int S = n;
	vector<vector<pair<int,int>>> adj(n);
	for(int i=0;i<m;i++){
		adj[u[i]].emplace_back(v[i],c[i]);
		adj[v[i]].emplace_back(u[i],c[i]);
	}
	vector<int> p(n);
	for(int x=0;x<n;x++){
		queue<int> q;
		vector<bool> visited(n);
		vector<vector<int>> advance(n);
		vector<bool> recieved(n);
		q.emplace(x);
		while(!q.empty()){
			auto curr = q.front();q.pop();
			if(visited[curr])continue;
			visited[curr]=true;
			p[x]++;
			if(!recieved[r[curr]]){
				recieved[r[curr]]=true;
				for(int&i:advance[r[curr]])q.emplace(i);
			}
			for(auto[i,col]:adj[curr])if(!visited[i]){
				if(recieved[col])q.emplace(i);
				else advance[col].emplace_back(i);
			}
		}
	}
	int ans = *min_element(p.begin(),p.end());
	cerr << "DEBUG Answer: " << ans << endl;
	vector<int> res(n);
	for(int i=0;i<n;i++)if(p[i]==ans)res[i]=1;
	return res;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:7:6: warning: unused variable 'S' [-Wunused-variable]
    7 |  int S = n;
      |      ^

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