Submission #1220058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220058		akqxolotl	Keys (IOI21_keys)	C++20	37 / 100	3093 ms	41692 KiB

keys

#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define debug(x) cerr<<#x<<" is "<<x<<endl;

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int n=r.size(),m=u.size();
	vector<int> p[n+1];
	vector<int> o[n];
	for(int i=0;i<m;i++){
		o[c[i]].pb(i);
	}
	//debug(n)debug(m)
	for(int i=0;i<n;i++){
		//debug(i)
		bool vis[n];
		set<int> adj[n];
		memset(vis,0,sizeof(vis));
		queue<int> q;
		set<int> k;
		q.push(i);
		int ans=0;
		while(!q.empty()){
			int t=q.front();
			//debug(t)
			q.pop();
			if(vis[t])continue;
			//debug(t)
			//if(i==0)debug(t)
			vis[t]=1;
			ans++;
			if(k.find(r[t])==k.end()){
				//debug(r[t])
				for(auto j:o[r[t]]){
					//debug(j)
					//if(u[j]>=n||v[j]>=n)debug(u[j])debug(v[j])
					if(adj[u[j]].find(v[j])!=adj[u[j]].end())continue;
					if(adj[v[j]].find(u[j])!=adj[v[j]].end())continue;
					adj[u[j]].insert(v[j]);
					adj[v[j]].insert(u[j]);
					//debug(v[j])debug(u[j])
					if(vis[u[j]]){
						if(!vis[v[j]])q.push(v[j]);
					}else if(vis[v[j]]){
						if(!vis[u[j]])q.push(u[j]);
					}
				}
				k.insert(r[t]);
			}
			for(auto j:adj[t]){
				if(!vis[j])q.push(j);
			}
			//debug(1)
			//debug(i)
		}
		//debug(ans)
		p[ans].pb(i);
	}
	vector<int> af;
	for(int i=0;i<n;i++)af.pb(0);
	for(int i=1;i<=n;i++){
		if(p[i].empty())continue;
		for(auto j:p[i]){
			af[j]=1;
		}
		return af;
	}
}

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:69:1: warning: control reaches end of non-void function [-Wreturn-type]
   69 | }
      | ^

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