oj.uz

Submission #789579

# Submission time Handle Problem Language Result Execution time Memory
789579 2023-07-21T14:10:55 Z Trunkty Keys (IOI21_keys) C++17
9 / 100
 460 ms 119972 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll

int n,m;
set<int> vals[300005];
map<int,vector<int>> roads[300005];
vector<int> tovis[300005];
bool vis[300005];
int curr[300005];

// DSU
int root[300005],siz[300005];

int findroot(int x){
	if(x!=root[x]){
		root[x] = findroot(root[x]);
	}
	return root[x];
}

void domerge(int a, int b){
	a = findroot(a);
	b = findroot(b);
	if(a==b){
		return;
	}
	if(siz[a]>siz[b]){
		swap(a,b);
	}
	root[a] = b;
	siz[b] += siz[a];
	for(int i:vals[a]){
		vals[b].insert(i);
	}
	vals[a].clear();
	for(int i:tovis[a]){
		tovis[b].push_back(i);
	}
	tovis[a].clear();
	for(pair<int,vector<int>> i:roads[a]){
		if(vals[b].find(i.first)!=vals[b].end()){
			for(int j:i.second){
				tovis[b].push_back(j);
			}
		}
		else{
			for(int j:i.second){
				roads[b][i.first].push_back(j);
			}
		}
	}
	roads[a].clear();
	curr[b] += curr[a];
}

int toret=-1;

void dfs(int x){
	if(curr[x]){
		toret = x;
		return;
	}
	vis[x] = true;
	curr[x]++;
	while(tovis[x].size()>0){
		int p = tovis[x].back();
		p = findroot(p);
		tovis[x].pop_back();
		dfs(p);
		if(toret!=-1){
			domerge(x,p);
			x = findroot(x);
			p = findroot(p);
			toret = findroot(toret);
			if(toret==x){
				toret = -1;
			}
			else{
				curr[x]--;
				return;
			}
		}
	}
	curr[x]--;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
	n = r.size();
	m = u.size();
	for(int i=0;i<=n-1;i++){
		vals[i].insert(r[i]);
		root[i] = i;
		siz[i] = 1;
	}
	for(int i=0;i<=m-1;i++){
		roads[u[i]][c[i]].push_back(v[i]);
		roads[v[i]][c[i]].push_back(u[i]);
	}
	bool one=false;
	for(int i=0;i<=n-1;i++){
		for(int j:roads[i][r[i]]){
			tovis[i].push_back(j);
		}
		roads[i][r[i]].clear();
		if(tovis[i].size()==0){
			one = true;
		}
	}
	if(one){
		vector<int> ret;
		for(int i=0;i<=n-1;i++){
			if(tovis[i].size()==0){
				ret.push_back(1);
			}
			else{
				ret.push_back(0);
			}
		}
		return ret;
	}
	for(int i=0;i<=n-1;i++){
		if(!vis[i] and root[i]==i){
			dfs(i);
		}
	}
	vector<int> ret;
	int mini=2e9;
	for(int i=0;i<=n-1;i++){
		if(siz[findroot(i)]==1){
			continue;
		}
		mini = min(mini,siz[findroot(i)]);
	}
	for(int i=0;i<=n-1;i++){
		if(siz[findroot(i)]==mini){
			ret.push_back(1);
		}
		else{
			ret.push_back(0);
		}
	}
	return ret;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35500 KB Output is correct
2 Correct 20 ms 35480 KB Output is correct
3 Correct 19 ms 35444 KB Output is correct
4 Correct 22 ms 35516 KB Output is correct
5 Correct 19 ms 35540 KB Output is correct
6 Correct 20 ms 35564 KB Output is correct
7 Correct 19 ms 35504 KB Output is correct
8 Correct 20 ms 35512 KB Output is correct
9 Correct 19 ms 35524 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35500 KB Output is correct
2 Correct 20 ms 35480 KB Output is correct
3 Correct 19 ms 35444 KB Output is correct
4 Correct 22 ms 35516 KB Output is correct
5 Correct 19 ms 35540 KB Output is correct
6 Correct 20 ms 35564 KB Output is correct
7 Correct 19 ms 35504 KB Output is correct
8 Correct 20 ms 35512 KB Output is correct
9 Correct 19 ms 35524 KB Output is correct
10 Correct 18 ms 35512 KB Output is correct
11 Correct 20 ms 35612 KB Output is correct
12 Correct 19 ms 35584 KB Output is correct
13 Correct 21 ms 35436 KB Output is correct
14 Correct 19 ms 35524 KB Output is correct
15 Incorrect 25 ms 35540 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35500 KB Output is correct
2 Correct 20 ms 35480 KB Output is correct
3 Correct 19 ms 35444 KB Output is correct
4 Correct 22 ms 35516 KB Output is correct
5 Correct 19 ms 35540 KB Output is correct
6 Correct 20 ms 35564 KB Output is correct
7 Correct 19 ms 35504 KB Output is correct
8 Correct 20 ms 35512 KB Output is correct
9 Correct 19 ms 35524 KB Output is correct
10 Correct 18 ms 35512 KB Output is correct
11 Correct 20 ms 35612 KB Output is correct
12 Correct 19 ms 35584 KB Output is correct
13 Correct 21 ms 35436 KB Output is correct
14 Correct 19 ms 35524 KB Output is correct
15 Incorrect 25 ms 35540 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35500 KB Output is correct
2 Correct 20 ms 35480 KB Output is correct
3 Correct 19 ms 35444 KB Output is correct
4 Correct 22 ms 35516 KB Output is correct
5 Correct 19 ms 35540 KB Output is correct
6 Correct 20 ms 35564 KB Output is correct
7 Correct 19 ms 35504 KB Output is correct
8 Correct 20 ms 35512 KB Output is correct
9 Correct 19 ms 35524 KB Output is correct
10 Correct 460 ms 110204 KB Output is correct
11 Incorrect 451 ms 119972 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35500 KB Output is correct
2 Correct 20 ms 35480 KB Output is correct
3 Correct 19 ms 35444 KB Output is correct
4 Correct 22 ms 35516 KB Output is correct
5 Correct 19 ms 35540 KB Output is correct
6 Correct 20 ms 35564 KB Output is correct
7 Correct 19 ms 35504 KB Output is correct
8 Correct 20 ms 35512 KB Output is correct
9 Correct 19 ms 35524 KB Output is correct
10 Correct 18 ms 35512 KB Output is correct
11 Correct 20 ms 35612 KB Output is correct
12 Correct 19 ms 35584 KB Output is correct
13 Correct 21 ms 35436 KB Output is correct
14 Correct 19 ms 35524 KB Output is correct
15 Incorrect 25 ms 35540 KB Output isn't correct
16 Halted 0 ms 0 KB -