Submission #811246

#	Time	Username	Problem	Language	Result	Execution time	Memory
811246		penguinman	Keys (IOI21_keys)	C++17	37 / 100	2980 ms	234108 KiB

keys

#include <vector>

#include <bits/stdc++.h>
 
using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
using std::endl;
 
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()

constexpr ll inf = (1ll<<60);

struct directed_graph{
	ll N;
	vii edge;
	vii revedge;
	vi par;
	vii member;
	directed_graph(ll n): N(n){
		edge.resize(N);
		revedge.resize(N);
	}
	void add_edge(ll u, ll v){
		edge[u].pb(v);
		revedge[v].pb(u);
	}
	vi ord, rev;
	vector<bool> flag;
	void dfs1(ll now){
		flag[now] = true;
		for(auto next: edge[now]){
			if(!flag[next]) dfs1(next);
		}
		ord.pb(now);
	}
	void dfs2(ll now, ll root){
		rev[now] = root;
		for(auto next: revedge[now]){
			if(rev[next] == -1) dfs2(next, root);
		}
	}
	vi SCC(){
		flag.resize(N);
		rev.resize(N,-1);
		ll cnt = 0;
		rep(i,0,N){
			if(!flag[i]) dfs1(i);
		}
		reverse(all(ord));
		for(auto i: ord){
			if(rev[i] == -1) dfs2(i, i);
		}
		return rev;
	}
};

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	ll N = r.size();
	vii edge(N), key(N);
	rep(i,0,u.size()){
		edge[u[i]].pb(v[i]);
		edge[v[i]].pb(u[i]);
		key[u[i]].pb(c[i]);
		key[v[i]].pb(c[i]);
	}
	vi par(N);
	ll Rmax = *max_element(all(r))+1;
	vector<vector<bool>> obtained(N,vector<bool>(Rmax));
	rep(i,0,N){
		par[i] = i;
		obtained[i][r[i]] = true;
	}
	ll ccnt = 0;
	while(true){
		assert(ccnt <= Rmax+10);
		ccnt++;
		directed_graph G(N);
		rep(i,0,N){
			rep(j,0,edge[i].size()){
				ll next = edge[i][j];
				if(par[next] == par[i]) continue;
				if(!obtained[par[i]][key[i][j]]) continue;
				G.add_edge(par[i],par[next]);
			}
		}
		{
			vi v;
			vector<bool> flag(N);
			rep(i,0,N){
				if(par[i] == i){
					if(G.edge[i].empty()){
						v.pb(i);
						flag[i] = true;
					}
				}
			}
			if(!v.empty()){
				vi member(N);
				rep(i,0,N){
					if(flag[par[i]]) member[par[i]]++;
				}
				ll min = inf;
				rep(i,0,N){
					if(member[i]) min = std::min(min, member[i]);
				}
				vector<int> ans(N);
				rep(i,0,N){
					if(member[par[i]] == min) ans[i] = 1;
				}
				return ans;
			}
		}
		par = G.SCC();
		rep(i,0,N) obtained[par[i]][r[i]] = true;
	}
}

Compilation message (stderr)

keys.cpp: In member function 'vi directed_graph::SCC()':
keys.cpp:58:6: warning: unused variable 'cnt' [-Wunused-variable]
   58 |   ll cnt = 0;
      |      ^~~

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