oj.uz

Submission #446647

# Submission time Handle Problem Language Result Execution time Memory
446647 2021-07-22T22:33:43 Z crackersamdjam Keys (IOI21_keys) C++17
9 / 100
 528 ms 124900 KB 
#if !defined(ONLINE_JUDGE) && !defined(LOCAL)
// oj.uz
#include "keys.h"
#endif

#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 outdeg[MM];

int dfn[MM], low[MM], t, id[MM];
bool ins[MM];
stack<int> stk;
vector<int> scc[MM];
set<int> newkeys[MM];
set<int> 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, bool same){
	if(a == b) return;
	// 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);
	newkeys[b].clear();

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

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

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

		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, 1);
		}
	}
}

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]);
				outdeg[id[i]] = 1;
			}
		}
	}

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

	for(auto rt: roots){
		pr("at", rt);
		while(size(newkeys[rt])){
			auto i = *newkeys[rt].begin();
			newkeys[rt].erase(i);
			if(donekeys[rt].count(i)) continue;
			donekeys[rt].insert(i);
			// to[rt][i] gets edited... not good
			auto old = to[rt][i];
			// for(auto u: to[rt][i]){

			pr("key", i);

			for(auto u: old){
				pr("m", rt, u);
				if(find(u) == find(rt)){
					merge(rt, u, 1);
				}
				else{
					merge(u, rt, 0);
					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);
		assert(size(res) == n);
		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 56652 KB Output is correct
2 Correct 36 ms 56576 KB Output is correct
3 Correct 35 ms 56628 KB Output is correct
4 Correct 36 ms 56724 KB Output is correct
5 Correct 35 ms 56636 KB Output is correct
6 Correct 40 ms 56656 KB Output is correct
7 Correct 37 ms 56608 KB Output is correct
8 Correct 35 ms 56644 KB Output is correct
9 Correct 35 ms 56732 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56652 KB Output is correct
2 Correct 36 ms 56576 KB Output is correct
3 Correct 35 ms 56628 KB Output is correct
4 Correct 36 ms 56724 KB Output is correct
5 Correct 35 ms 56636 KB Output is correct
6 Correct 40 ms 56656 KB Output is correct
7 Correct 37 ms 56608 KB Output is correct
8 Correct 35 ms 56644 KB Output is correct
9 Correct 35 ms 56732 KB Output is correct
10 Correct 36 ms 56632 KB Output is correct
11 Correct 35 ms 56644 KB Output is correct
12 Correct 36 ms 56652 KB Output is correct
13 Correct 36 ms 56612 KB Output is correct
14 Correct 35 ms 56616 KB Output is correct
15 Correct 39 ms 56760 KB Output is correct
16 Correct 36 ms 56580 KB Output is correct
17 Incorrect 35 ms 56652 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56652 KB Output is correct
2 Correct 36 ms 56576 KB Output is correct
3 Correct 35 ms 56628 KB Output is correct
4 Correct 36 ms 56724 KB Output is correct
5 Correct 35 ms 56636 KB Output is correct
6 Correct 40 ms 56656 KB Output is correct
7 Correct 37 ms 56608 KB Output is correct
8 Correct 35 ms 56644 KB Output is correct
9 Correct 35 ms 56732 KB Output is correct
10 Correct 36 ms 56632 KB Output is correct
11 Correct 35 ms 56644 KB Output is correct
12 Correct 36 ms 56652 KB Output is correct
13 Correct 36 ms 56612 KB Output is correct
14 Correct 35 ms 56616 KB Output is correct
15 Correct 39 ms 56760 KB Output is correct
16 Correct 36 ms 56580 KB Output is correct
17 Incorrect 35 ms 56652 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56652 KB Output is correct
2 Correct 36 ms 56576 KB Output is correct
3 Correct 35 ms 56628 KB Output is correct
4 Correct 36 ms 56724 KB Output is correct
5 Correct 35 ms 56636 KB Output is correct
6 Correct 40 ms 56656 KB Output is correct
7 Correct 37 ms 56608 KB Output is correct
8 Correct 35 ms 56644 KB Output is correct
9 Correct 35 ms 56732 KB Output is correct
10 Correct 528 ms 124900 KB Output is correct
11 Incorrect 313 ms 107616 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 56652 KB Output is correct
2 Correct 36 ms 56576 KB Output is correct
3 Correct 35 ms 56628 KB Output is correct
4 Correct 36 ms 56724 KB Output is correct
5 Correct 35 ms 56636 KB Output is correct
6 Correct 40 ms 56656 KB Output is correct
7 Correct 37 ms 56608 KB Output is correct
8 Correct 35 ms 56644 KB Output is correct
9 Correct 35 ms 56732 KB Output is correct
10 Correct 36 ms 56632 KB Output is correct
11 Correct 35 ms 56644 KB Output is correct
12 Correct 36 ms 56652 KB Output is correct
13 Correct 36 ms 56612 KB Output is correct
14 Correct 35 ms 56616 KB Output is correct
15 Correct 39 ms 56760 KB Output is correct
16 Correct 36 ms 56580 KB Output is correct
17 Incorrect 35 ms 56652 KB Output isn't correct
18 Halted 0 ms 0 KB -