제출 #821560

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
821560		alvingogo	열쇠 (IOI21_keys)	C++17	100 / 100	375 ms	129516 KiB

keys

#include <vector>
#include <bits/stdc++.h>
#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