제출 #1229208

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

keys

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

#define int long long 
#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;

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);
    } 
    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]) dfs1(u);
	topo.push_back(x);
}

void dfs2(int x){
	if(visited[x]==2) return;
	visited[x]=2;
	for (auto u : neighu[x]) {
		if(visited[u]==2) 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) {
	vector<int> r(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]=(1LL<<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++) {
			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(ed.find({min(geP(u[i]),geP(v[i])),max(geP(u[i]),geP(v[i]))})==ed.end()) ed[{min(geP(u[i]),geP(v[i])),max(geP(u[i]),geP(v[i]))}]=0;
			ed[{min(geP(u[i]),geP(v[i])),max(geP(u[i]),geP(v[i]))}]|=(1LL<<(int)c[i]);
		}
		for (auto u : ed)
		{
			if(r[geP(u.first.first)]&u.second){
				neigh[geP(u.first.first)].push_back(geP(u.first.second));
				neighu[geP(u.first.second)].push_back(geP(u.first.first));
			}if(r[geP(u.first.second)]&u.second){
				neigh[geP(u.first.second)].push_back(geP(u.first.first));
				neighu[geP(u.first.first)].push_back(geP(u.first.second));
			}
		}
		for (int i = 0; i < n; i++) dfs1(geP(i));
		for (int i = 0; i < n; i++){
			dfs2(geP(topo[(n-1)-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)]);
	}

	return ans;
}

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