Submission #821607

#	Time	Username	Problem	Language	Result	Execution time	Memory
821607		alvingogo	Keys (IOI21_keys)	C++17	100 / 100	354 ms	118860 KiB

keys

/* 
hack test:
11 13
0 1 2 3 3 3 3 3 3 2 1
1 10 1
10 0 1
0 2 1
2 9 2
9 0 2
2 3 1
3 4 3
4 5 3
5 6 3
6 7 3
7 8 3
8 3 3
0 1 0

*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct DSU{
	vector<int> bo;
	void init(int n){
		bo.resize(n);
		iota(bo.begin(),bo.end(),0);
	}
	int find(int x){
		return bo[x]==x?x:bo[x]=find(bo[x]);
	}
	void merge(int x,int y){
		bo[x]=y;
	}
}dsu;
vector<int> r,dfn,low,out,inv;
vector<vector<int> > nw;
vector<vector<pair<int,int> > > e;
vector<vector<pair<int,int> > > st;
int cnt=1;
void dfs(int a,int f){
	dfn[a]=low[a]=out[a]=cnt;
	inv[cnt]=a;
	cnt++;
	for(auto h:e[a]){
		st[h.fs].push_back({a,h.sc});
	}
	for(auto h:st[r[a]]){
		nw[dsu.find(h.fs)].push_back(h.sc);
	}
	st[r[a]].clear();
	while(nw[a].size()){
		auto h=nw[a].back();
		nw[a].pop_back();
		if(dfn[h]){
			low[a]=min(low[a],dfn[h]);
			continue;
		}
		dfs(h,a);
		low[a]=min(low[a],low[h]);
		out[a]=out[h];
		for(auto h:st[r[a]]){
			nw[dsu.find(h.fs)].push_back(h.sc);
		}
		st[r[a]].clear();
	}
	dsu.merge(a,f);
}
vector<int> find_reachable(vector<int> R, vector<int> u, vector<int> v, vector<int> c) {
	int n=R.size();
	int m=u.size();
	dsu.init(n);
	e.resize(n);
	dfn.resize(n);
	low.resize(n);
	nw.resize(n);
	out.resize(n);
	inv.resize(n+1);
	st.resize(n);
	r=R;
	for(int i=0;i<m;i++){
		e[u[i]].push_back({c[i],v[i]});
		e[v[i]].push_back({c[i],u[i]});
	}
	for(int i=0;i<n;i++){
		if(!dfn[i]){
			dfs(i,i);
		}
	}
	int mn=1e9;
	for(int i=0;i<n;i++){
		if(dfn[i]==low[i]){
			mn=min(mn,out[i]-dfn[i]+1);
		}
	}
	vector<int> ans(n);
	for(int i=0;i<n;i++){
		if(dfn[i]==low[i]){
			if(out[i]-dfn[i]+1==mn){
				for(int j=dfn[i];j<=out[i];j++){
					ans[inv[j]]=1;
				}
			}
		}
	}
	return ans;
}

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