Submission #1044404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044404		Unforgettablepl	Keys (IOI21_keys)	C++17	20 / 100	1123 ms	123440 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;
	map<pair<int,int>,int> lookup;
	vector<vector<int>> adj(n);
	vector<vector<int>> readj(n);
	for(int i=0;i<n;i++){
		lookup[{i,r[i]}]=i;
	}
	for(int i=0;i<m;i++){
		if(lookup.count({u[i],c[i]})==0){
			lookup[{u[i],c[i]}]=S;
			adj.emplace_back();
			readj.emplace_back();
			adj[S].emplace_back(u[i]);
			readj[u[i]].emplace_back(S);
			S++;
		}
		if(lookup.count({v[i],c[i]})==0){
			lookup[{v[i],c[i]}]=S;
			adj.emplace_back();
			readj.emplace_back();
			adj[S].emplace_back(v[i]);
			readj[v[i]].emplace_back(S);
			S++;
		}
		int actu = lookup[{u[i],c[i]}];
		int actv = lookup[{v[i],c[i]}];
		adj[actu].emplace_back(actv);
		readj[actv].emplace_back(actu);
		adj[actv].emplace_back(actu);
		readj[actu].emplace_back(actv);
	}
	vector<int> order;
	vector<bool> visited(S);
	{
		function<void(int)> dfs = [&](int x){
			if(visited[x])return;
			visited[x]=true;
			for(int&i:adj[x])dfs(i);
			order.emplace_back(x);
		};
		for(int i=0;i<S;i++)dfs(i);
		reverse(order.begin(),order.end());
	}
	vector<vector<int>> components = {{}};
	vector<int> mycompo(S);
	vector<bool> disq(1);
	function<void(int,int)> dfs = [&](int x,int compo){
		if(mycompo[x]){
			if(mycompo[x]!=compo)disq[mycompo[x]]=true;
			return;
		}
		mycompo[x]=compo;
		if(x<n)components[compo].emplace_back(x);
		for(int&i:readj[x])dfs(i,compo);
	};
	int compocnt = 0;
	for(int&i:order){
		if(mycompo[i])continue;
		disq.emplace_back(false);
		components.emplace_back();
		dfs(i,++compocnt);
	}
	int ans = n;
	for(int i=1;i<=compocnt;i++){
		if(!disq[i])ans=min(ans,(int)components[i].size());
	}
	vector<int> res(n);
	for(int i=1;i<=compocnt;i++){
		if(disq[i])continue;
		if(components[i].size()>ans)continue;
		for(int&x:components[i])res[x]=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:76:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |   if(components[i].size()>ans)continue;
      |      ~~~~~~~~~~~~~~~~~~~~^~~~

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