제출 #1166046

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166046		KG07	Keys (IOI21_keys)	C++20	9 / 100	198 ms	226512 KiB

keys

#include <bits/stdc++.h>
using namespace std;
int a[300003], s[300003];
bool b[300003], B[300003], C[300003];
vector<pair<int, int>> A[300003];
queue<int> p, P, q, Q[300003];
int find(int x){
	if(!a[x])return x;
	return a[x] = find(a[x]);
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int N = r.size();
	int M = c.size();
	for(int i = 0; i < M; i++){
		A[u[i]+1].push_back(make_pair(v[i]+1, c[i]));
		A[v[i]+1].push_back(make_pair(u[i]+1, c[i]));
	}
	int T = 20;
	while(T--){
		for(int t = 1; t <= N; t++){
			if(a[t] || C[t])continue;
			q.push(t);
			while(!q.empty()){
				int h = q.front();
				q.pop();
				if(B[h])continue;
				if(find(h) != t){
					a[t] = h;
					C[find(t)] = true;
					while(!q.empty())q.pop();
					break;
				}
				B[h] = true;
				P.push(h);
				if(!b[r[h-1]]){
					while(!Q[r[h-1]].empty()){
						q.push(Q[r[h-1]].front());
						Q[r[-1]].pop();
					}
					b[r[h-1]] = true;
					p.push(r[h-1]);
				}
				for(int i = 0; i < A[h].size(); i++){
					p.push(A[h][i].second);
					if(b[A[h][i].second])q.push(A[h][i].first);
					else Q[A[h][i].second].push(A[h][i].first);
				}
			}
			while(!p.empty()){
				int h = p.front();
				p.pop();
				b[h] = false;
				while(!Q[h].empty())Q[h].pop();
			}
			while(!P.empty()){
				int h = P.front();
				P.pop();
				B[h] = false;
			}
		}
		for(int i = 1; i <= N; i++)C[i] = false;
		//for(int i = 1; i <= N; i++)cout << a[i] << " ";cout << "\n";
	}
	for(int t = 1; t <= N; t++){
		if(a[t])continue;
		q.push(t);
		while(!q.empty()){
			int h = q.front();
			q.pop();
			if(B[h])continue;
			B[h] = true;
			s[t]++;
			P.push(h);
			if(!b[r[h-1]]){
				while(!Q[r[h-1]].empty()){
					q.push(Q[r[h-1]].front());
					Q[r[-1]].pop();
				}
				b[r[h-1]] = true;
				p.push(r[h-1]);
			}
			for(int i = 0; i < A[h].size(); i++){
				p.push(A[h][i].second);
				if(b[A[h][i].second])q.push(A[h][i].first);
				else Q[A[h][i].second].push(A[h][i].first);
			}
		}
		while(!p.empty()){
			int h = p.front();
			p.pop();
			b[h] = false;
			while(!Q[h].empty())Q[h].pop();
		}
		while(!P.empty()){
			int h = P.front();
			P.pop();
			B[h] = false;
			s[h] = s[t];
		}
	}
	int z = N;
	for(int i = 1; i <= N; i++)if(s[i])z=min(z, s[i]);
	//for(int i = 1; i <= N; i++)cout << s[i] << " ";
	vector<int> S;
	for(int i = 1; i <= N; i++)S.push_back(s[i]==z?1:0);
	return S;
}

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