제출 #1229235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229235		Ludissey	열쇠 (IOI21_keys)	C++20	9 / 100	3098 ms	101976 KiB

keys

#include <bits/stdc++.h>
 
using namespace std;

#define all(a) (a.begin(), a.end())
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int)a.size()

vector<int> sz,parent;
vector<vector<int>> neigh;
vector<vector<int>> neighu;
vector<int> topo;
vector<int> visited;
bool unt=true;
vector<int> r;

int geP(int a){
    if(parent[a]==a) return a;
    return parent[a]=geP(parent[a]);
}

void unite(int a, int b){
    a=geP(a);
    b=geP(b);
    if(a==b) return;
    if(sz[a]<sz[b]){
        swap(a,b);
    } 
	r[a]|=r[b];
    sz[a]+=sz[b];
    parent[b]=a;
}

bool same(int a, int b){
    a=geP(a);
    b=geP(b);
    return (a==b);
}

void dfs1(int x){
	if(visited[x]==1) return;
	visited[x]=1;
	for (auto u : neigh[x]) {
		u=geP(u);
		if(same(u,x)) continue;
		dfs1(u);
	}
	topo.push_back(x);
}

void dfs2(int x){
	if(visited[x]==2) return;
	visited[x]=2;
	for (auto u : neighu[x]) {
		u=geP(u);
		if(visited[u]==2) continue;
		if(same(u,x)) continue;
		unite(u,x);
		unt=true;
 		dfs2(u);
	}
}


std::vector<signed> find_reachable(std::vector<signed> _r, std::vector<signed> u, std::vector<signed> v, std::vector<signed> c) {
	r.resize(sz(_r));
	int n=sz(r);
	for (int i = 0; i < n; i++)
	{
		r[i]=_r[i];
	}
	
	std::vector<signed> ans(n, 1);
	neigh.resize(n);
	neighu.resize(n);
	for (int i = 0; i < sz(r); i++) r[i]=(1<<r[i]);
	sz.resize(n,1);
    parent.resize(n);
    visited.resize(n);
	topo.resize(n);
    for (int i = 0; i < n; i++) parent[i]=i;
    for (int i = 0; i < n; i++) sz[i]=1;
	unt=true;
	while(unt){
		unt=false;
		topo.clear();
		for (int i = 0; i < n; i++) {
			visited[i]=0;
		}
		for (int i = 0; i < sz(u); i++)
		{
			if(same(geP(u[i]),geP(v[i]))) continue;
			if(r[geP(u[i])]&(1<<c[i])){
				neigh[geP(u[i])].push_back(geP(v[i]));
				neighu[geP(v[i])].push_back(geP(u[i]));
			}
			if(r[geP(v[i])]&(1<<c[i])){
				neigh[geP(v[i])].push_back(geP(u[i]));
				neighu[geP(u[i])].push_back(geP(v[i]));
			}
		}
		for (int i = 0; i < n; i++) dfs1(geP(i));
		for (int i = 0; i < n; i++){
			dfs2(geP(topo[(n-1)-i]));
		}
	}
	topo.clear();
	for (int i = 0; i < n; i++) {
		neigh[i].clear();
		neighu[i].clear();
		visited[i]=0;
	}
	for (int i = 0; i < n; i++) r[geP(i)]|=r[i];
	map<pair<int,int>,int> ed;
	for (int i = 0; i < sz(u); i++)
	{
		if(same(geP(u[i]),geP(v[i]))) continue;
		if(r[geP(u[i])]&(1<<c[i])){
			neigh[geP(u[i])].push_back(geP(v[i]));
		}
		if(r[geP(v[i])]&(1<<c[i])){
			neigh[geP(v[i])].push_back(geP(u[i]));
		}
	}
	int mn=1e9;
	for (int i = 0; i < n; i++){
		if(sz(neigh[geP(i)])==0) mn=min(sz[geP(i)],mn);
	}
	for (int i = 0; i < n; i++){
		ans[i]=(mn==sz[geP(i)]&&sz(neigh[geP(i)])==0);
	}

	return ans;
}

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