제출 #435494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435494		errorgorn	Keys (IOI21_keys)	C++17	37 / 100	222 ms	16460 KiB

keys

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
 
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
 
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n,m;
int type[2005];
 
vector<int> keys[2005];
vector<int> vertice[2005];
int dest[4005];
 
vector<int> proc;
bool vis[2005];
bool vis_key[2005];
int cnt[4005];
 
int reach(int i){
	memset(vis,false,sizeof(vis));
	memset(vis_key,false,sizeof(vis_key));
	memset(cnt,0,sizeof(cnt));
 
	proc={i};
 
	int ans=0;
	while (!proc.empty()){
		int v=proc.back(); proc.pob();
		if (vis[v]) continue;
		vis[v]=true;
		ans++;
 
		for (auto &it:vertice[v]){
			cnt[it]++;
			if (cnt[it]==2) proc.pub(dest[it]);
		}
 
		if (!vis_key[type[v]]){
			vis_key[type[v]]=true;
			for (auto &it:keys[type[v]]){
				cnt[it]++;
				if (cnt[it]==2) proc.pub(dest[it]);
			}
		}
	}
 
	//cout<<i<<" "<<ans<<endl;
	return ans;
}
 
std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
	n=sz(R),m=sz(U);
 
	rep(x,0,n) type[x]=R[x];
 
	rep(x,0,m){
		keys[C[x]].pub(x*2);
		vertice[U[x]].pub(x*2);
		dest[x*2]=V[x];
 
		keys[C[x]].pub(x*2+1);
		vertice[V[x]].pub(x*2+1);
		dest[x*2+1]=U[x];
	}
 
	vector<int> ans;
	int best=1e9;
 
	rep(x,0,n){
		auto temp=reach(x);
		if (best>temp) best=temp,ans.clear();
		if (best==temp) ans.pub(x);
	}
 
	vector<int> res(n,0);
	for (auto &it:ans) res[it]=1;
 
	return res;
}

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