oj.uz

Submission #446632

# Submission time Handle Problem Language Result Execution time Memory
446632 2021-07-22T21:37:14 Z crackersamdjam Keys (IOI21_keys) C++17
9 / 100
 1548 ms 2097156 KB 
#include "keys.h"

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()

#ifdef LOCAL
template<typename T> void pr(T a){std::cerr<<a<<std::endl;}
template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args> void pr(Args... args){}
#endif

using namespace std;
using pii = pair<int, int>;
int constexpr MM = 3e5+5;

int n, m;

vector<int> r;

vector<int> adj[MM];
vector<int> adj2[MM];

int dfn[MM], low[MM], t, id[MM];
bool ins[MM];
stack<int> stk;
vector<int> scc[MM];
set<int> newkeys[MM], donekeys[MM];
map<int, vector<int>> to[MM];

// which weakly connected component
// this is different from id[], which is scc "root"
int par[MM];

int find(int x){
	while(x != par[x])
		x = par[x], par[x] = par[par[x]];
	return x;
}

void merge(int a, int b){
	// merges b into a
	if(size(newkeys[b]) > size(newkeys[a]))
		swap(newkeys[a], newkeys[b]);
	for(auto i: newkeys[b])
		newkeys[a].insert(i);

	if(size(donekeys[b]) > size(donekeys[a]))
		swap(donekeys[a], donekeys[b]);
	for(auto i: donekeys[b])
		donekeys[a].insert(i);

	if(size(to[a]) > size(to[b]))
		swap(to[a], to[b]);
	for(auto &[i, v]: to[b]){
		to[a][i].insert(to[a][i].end(), all(v));
	}

	if(size(scc[a]) > size(scc[b]))
		swap(scc[a], scc[b]);
	scc[a].insert(scc[a].end(), all(scc[b]));

	par[find(b)] = find(a);
}

void dfs(int cur){
	dfn[cur] = low[cur] = ++t;
	stk.push(cur);
	ins[cur] = 1;
	
	for(auto u: adj[cur]){
		if(!dfn[u]){
			dfs(u);
			low[cur] = min(low[cur], low[u]);
		}
		else if(ins[u])
			low[cur] = min(low[cur], dfn[u]);
	}
	
	if(dfn[cur] == low[cur]){
		int u = -1;
		while(u != cur){
			u = stk.top(); stk.pop();
			ins[u] = 0;
			id[u] = cur;
			merge(cur, u);
		}
	}
}

vector<int> find_reachable(vector<int> _r, vector<int> a, vector<int> b, vector<int> c){
	r = move(_r);
	n = size(r);
	m = size(a);
	vector<int> res(n);

	for(int i = 0; i < m; i++){
		if(c[i] == r[a[i]]){
			adj[a[i]].emplace_back(b[i]);
			// pr("edge", a[i], b[i]);
		}
		else{
			to[a[i]][c[i]].emplace_back(b[i]);
		}
		if(c[i] == r[b[i]]){
			adj[b[i]].emplace_back(a[i]);
			// pr("edge", a[i], b[i]);
		}
		else{
			to[b[i]][c[i]].emplace_back(a[i]);
		}
	}

	for(int i = 0; i < n; i++){
		par[i] = i;
		newkeys[i].insert(r[i]);
		scc[i].emplace_back(i);
	}

	for(int i = 0; i < n; i++){
		if(!dfn[i]){
			dfs(i);
		}
	}

	for(int i = 0; i < n; i++){
		for(int j: adj[i]){
			if(id[i] != id[j]){
				adj2[id[i]].emplace_back(id[j]);
			}
		}
	}

	// each scc root...
	vector<int> roots;
	for(int i = 0; i < n; i++){
		if(!size(adj2[i])){
			roots.emplace_back(i);
			pr("add rt", i);
		}
	}

	for(auto rt: roots){
		while(size(newkeys[rt])){
			auto i = *newkeys[rt].begin();
			newkeys[rt].erase(i);
			if(donekeys[rt].count(i)) continue;
			donekeys[rt].insert(i);
			for(auto u: to[rt][i]){
				if(find(u) == find(rt)){
					merge(rt, u);
				}
				else{
					merge(u, rt);
					break;
				}
			}
		}
	}

	int ans = 1e9;
	for(auto rt : roots){
		if(find(rt) == rt){
			int s = size(scc[rt]);
			pr("check sz", rt, s);
			if(s < ans){
				ans = s;
			}
		}
	}
	for(auto rt : roots){
		if(find(rt) == rt){
			int s = size(scc[rt]);
			if(s == ans){
				pr("scc", rt);
				for(auto j: scc[rt]){
					pr("j", j);
					res[j] = 1;
				}
			}
		}
	}
	return res;
}

#ifdef LOCAL
namespace me{
	void go(){
		int n, m;
		cin>>n>>m;
		vector<int> r(n), a(m), b(m), c(m);
		for(int i = 0; i < n; i++)
			cin>>r[i];
		for(int i = 0; i < m; i++){
			cin>>a[i]>>b[i]>>c[i];
		}
		auto res = find_reachable(r, a, b, c);
		for(int i = 0; i < size(res); i++)
			cout<<res[i]<<' ';
	}
}
int main(){
	me::go();
}
#endif

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 63716 KB Output is correct
2 Correct 35 ms 63660 KB Output is correct
3 Correct 35 ms 63648 KB Output is correct
4 Correct 35 ms 63716 KB Output is correct
5 Correct 35 ms 63720 KB Output is correct
6 Correct 35 ms 63732 KB Output is correct
7 Correct 35 ms 63692 KB Output is correct
8 Correct 35 ms 63728 KB Output is correct
9 Correct 35 ms 63692 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 63716 KB Output is correct
2 Correct 35 ms 63660 KB Output is correct
3 Correct 35 ms 63648 KB Output is correct
4 Correct 35 ms 63716 KB Output is correct
5 Correct 35 ms 63720 KB Output is correct
6 Correct 35 ms 63732 KB Output is correct
7 Correct 35 ms 63692 KB Output is correct
8 Correct 35 ms 63728 KB Output is correct
9 Correct 35 ms 63692 KB Output is correct
10 Correct 35 ms 63692 KB Output is correct
11 Correct 35 ms 63684 KB Output is correct
12 Correct 38 ms 63692 KB Output is correct
13 Correct 35 ms 63676 KB Output is correct
14 Correct 35 ms 63732 KB Output is correct
15 Runtime error 1548 ms 2097156 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 63716 KB Output is correct
2 Correct 35 ms 63660 KB Output is correct
3 Correct 35 ms 63648 KB Output is correct
4 Correct 35 ms 63716 KB Output is correct
5 Correct 35 ms 63720 KB Output is correct
6 Correct 35 ms 63732 KB Output is correct
7 Correct 35 ms 63692 KB Output is correct
8 Correct 35 ms 63728 KB Output is correct
9 Correct 35 ms 63692 KB Output is correct
10 Correct 35 ms 63692 KB Output is correct
11 Correct 35 ms 63684 KB Output is correct
12 Correct 38 ms 63692 KB Output is correct
13 Correct 35 ms 63676 KB Output is correct
14 Correct 35 ms 63732 KB Output is correct
15 Runtime error 1548 ms 2097156 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 63716 KB Output is correct
2 Correct 35 ms 63660 KB Output is correct
3 Correct 35 ms 63648 KB Output is correct
4 Correct 35 ms 63716 KB Output is correct
5 Correct 35 ms 63720 KB Output is correct
6 Correct 35 ms 63732 KB Output is correct
7 Correct 35 ms 63692 KB Output is correct
8 Correct 35 ms 63728 KB Output is correct
9 Correct 35 ms 63692 KB Output is correct
10 Correct 672 ms 140712 KB Output is correct
11 Runtime error 546 ms 337736 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 63716 KB Output is correct
2 Correct 35 ms 63660 KB Output is correct
3 Correct 35 ms 63648 KB Output is correct
4 Correct 35 ms 63716 KB Output is correct
5 Correct 35 ms 63720 KB Output is correct
6 Correct 35 ms 63732 KB Output is correct
7 Correct 35 ms 63692 KB Output is correct
8 Correct 35 ms 63728 KB Output is correct
9 Correct 35 ms 63692 KB Output is correct
10 Correct 35 ms 63692 KB Output is correct
11 Correct 35 ms 63684 KB Output is correct
12 Correct 38 ms 63692 KB Output is correct
13 Correct 35 ms 63676 KB Output is correct
14 Correct 35 ms 63732 KB Output is correct
15 Runtime error 1548 ms 2097156 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -