제출 #827803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
827803		Supersonic	열쇠 (IOI21_keys)	C++17	0 / 100	4 ms	7296 KiB

keys

#include <vector>
#include <bits/stdc++.h>
using namespace std;
int n;
vector<pair<int,int>> g[300001];
int cmp[300001];
int tal[300001];
void flood(int x,int c){
	cmp[x]=c;
	tal[cmp[x]]++;
	for(auto i:g[x])if(!cmp[i.first])flood(i.first,c);
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	n=r.size();
	for(int i=0;i<n;i++){g[u[i]].push_back({v[i],c[i]});g[v[i]].push_back({u[i],c[i]});}
	vector<int> ans(n);
	bool f=0;
	for(int i=0;i<n;i++){
		ans[i]=0;
		if(r[i]!=0){f=1;ans[i]=1;}
	}
	if(f==0){
		int cc=1;
		for(int i=0;i<n;i++){if(cmp[i])continue;flood(i,cc);cc++;}
		int talm=1e9;
		for(int i=0;i<n;i++)if(tal[i]>0)talm=min(tal[i],talm);
		for(int i=0;i<n;i++)if(tal[cmp[i]]==talm)ans[i]=1;
	}
	return ans;
}

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