Submission #1215490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215490		thelegendary08	Keys (IOI21_keys)	C++17	9 / 100	3094 ms	29652 KiB

keys

#include "keys.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define mp make_pair
#define pb push_back
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define pii pair<int,int>
#define dout(x) cout<<x<<' '<<#x<<'\n';
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<'\n';
#define vvi vector<vi>
#define vb vector<bool>
using namespace std;
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();
	int m = u.size();
	vi ans(n);
	vvi adj(n);
	vvi edgcol(n);
	vvi edgnode(n);
	f0r(i,m){
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
		edgcol[c[i]].pb(i);
		edgnode[u[i]].pb(i);
		edgnode[v[i]].pb(i);
	}
	
	vi cnts;
	f0r(i,n){
		vi req(m);
		queue<int>q;
		q.push(i);
		vb vis(n);
		/*
		vis[i] = 1;
		for(auto x : edgnode[i]){
			req[x]++;
		}
		*/
		set<int>col;
		while(!q.empty()){
			int node = q.front(); q.pop();
			vis[node] = 1;
			if(!col.count(r[node])){
				col.insert(r[node]); 
				for(auto x : edgcol[r[node]]){
					req[x]++; 
					if(req[x] == 2){
						if(!vis[u[x]]){
							q.push(u[x]);
						}
						if(!vis[v[x]]){
							q.push(v[x]);
						}
					}
				}
			}
			
				
			for(auto x : edgnode[node]){
				if(!vis[u[x]] || !vis[v[x]]){
					req[x]++;
					if(req[x] == 2){
						if(!vis[u[x]]){
							q.push(u[x]);
						}
						if(!vis[v[x]]){
							q.push(v[x]);
						}
					}
				}
			}
			
		}
		
		// vout(vis);
		int cnt = 0;
		f0r(i,n){
			if(vis[i])cnt++;
		}
		cnts.pb(cnt);
		
	}
	// vout(cnts);
	int mn = *min_element(cnts.begin(), cnts.end());
	f0r(i,n){
		if(cnts[i] == mn)ans[i] = 1;
	}
	return ans;
}

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