Submission #1231323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231323		Ludissey	Keys (IOI21_keys)	C++20	37 / 100	1010 ms	2162688 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()

const int MAXN=200000;
vector<int> sz,parent;
vector<vector<int>> neigh;
vector<vector<int>> neighu;
vector<int> topo;
vector<bitset<MAXN>> r;
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;
	r[a]|=r[b];
}

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;
		unt=true;
		dfs2(u);
		unite(u,x);
	}
}


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]]=1;
	std::vector<signed> ans(n, 1);
	neigh.resize(n);
	neighu.resize(n);
	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;
	int rem=30;
	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 < sz(u); i++)
		{
			if(same(geP(u[i]),geP(v[i]))) continue;
			if(r[geP(u[i])][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])][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++) {
			if(i==geP(i)) dfs1(i);
		}
		for (int i = sz(topo)-1; i >= 0; i--){
			dfs2(topo[i]);
		}
		rem--;
		if(rem<=0) break;
	}
	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: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33