oj.uz

Submission #596769

# Submission time Handle Problem Language Result Execution time Memory
596769 2022-07-15T03:40:09 Z balbit Keys (IOI21_keys) C++17
100 / 100
 1399 ms 247528 KB 
#include <vector>
#include <bits/stdc++.h>
#ifndef BALBIT
#include "keys.h"
#endif
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
 
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
 
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define pb push_back
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
 
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#endif // BALBIT


const int maxn = 3e5+5;
int /*head[maxn], */par[maxn];
// int szedges[maxn]; // size of number of edges left

unordered_map<int, vector<int> > E[maxn]; // edges not done being worked
unordered_set<int> todo[maxn];
unordered_set<int> owned[maxn]; // todo is a subset of owned
vector<int> nhere[maxn]; // nodes in this unordered_set

int find(int x){return x == par[x]? x : par[x] = find(par[x]);}
inline int WHO(int x){return find(x);}

int dead[maxn]; // 1: this head is dead, 2: this head touches a dead, so it's super dead

int getone(int v) {
	while (!todo[v].empty()) {
		int c = *todo[v].begin();
		if (!E[v].count(c)) {
			todo[v].erase(c); continue;
		}
		// bug(v,c,SZ(E[v][c]));
		while (SZ(E[v][c])) {
			int go = WHO(E[v][c].back());
			E[v][c].pop_back();
			if (dead[go]) {
				bug(v, go, "dead!");
				return -2;
			}
			if (go != v) bug(v,go);
			if (go!=v) return go;
		}
		E[v].erase(c); todo[v].erase(c);
	}
	return -1;
}

void mrg(int a, int b, int newhead) {
	if (SZ(nhere[a]) < SZ(nhere[b])) swap(a,b);
	// a is the greater one
	for (int x : owned[b]) {
		if (owned[a].insert(x).s) {
			if (E[a].count(x)) {
				todo[a].insert(x);
			}
		}
	}
	for (auto &p : E[b]) {
		if (owned[a].count(p.f)) todo[a].insert(p.f); // consider merging todo later (?)
		E[a][p.f].insert(E[a][p.f].end(), ALL(p.s));
	}
	nhere[a].insert(nhere[a].end(), ALL(nhere[b]));

	unordered_map<int, vector<int> >().swap(E[b]);
	unordered_set<int>().swap(owned[b]);
	unordered_set<int>().swap(todo[b]);
	vector<int>().swap(nhere[b]);

	if (newhead != a) {
		assert(newhead == b);
		E[a].swap(E[b]);
		owned[a].swap(owned[b]);
		todo[a].swap(todo[b]);
		nhere[a].swap(nhere[b]);
		par[a] = b;
	}else{
		par[b] = a;
	}
}

vector<int> stk;
bool instk[maxn];

void runstack(){
	while (!stk.empty()) {
		int v = stk.back();
		int to = getone(v);
		assert(to != v);
		if (to == -1) {
			dead[v] = 1;
			instk[v] = 0;
			stk.pop_back();
			to = -2;
		}
		if (to == -2) {
			for (int e : stk) {
				dead[e] = 2; 
				instk[e] = 0;
			}
			stk.clear();
			return;
		}
		if (!instk[to]) {
			instk[to] = 1;
			stk.pb(to);
			continue;
		}else{
			while (stk.back() != to) {
				int last = stk.back(); instk[last] = 0; stk.pop_back();
				int pl = stk.back();
				mrg(last, pl, pl);
			}

		}
	}

}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	std::vector<int> ans(r.size(), 1);
	int n = SZ(r);
	int m = SZ(u);

	REP(i,m) {
		int U = u[i], V = v[i], C = c[i];
		REP(barbar, 2) {
			E[U][C].pb(V);
			swap(U,V);
		}
	}

	REP(i,n) {
		par[i] = i;
		nhere[i].pb(i);
		owned[i].insert(r[i]);
		if (E[i].count(r[i])) {
			todo[i].insert(r[i]);
			bug(i, "todo", r[i]);
		}
	}


	REP(i,n) {
		if (!dead[i]) {
			instk[i] = 1;
			stk.pb(i);
			runstack();
		}
	}

	vector<int> raw(n, n+1);

	REP(i,n) {
		int FI = find(i);
		bug(i, dead[i], FI);
		if (FI == i && dead[i] != 2) {
			for (int e : nhere[i]) {
				raw[e] = SZ(nhere[i]);
			}
		}
	}

	REP(i,n) {
		bug(i, raw[i]);
	}

	int mne = *min_element(ALL(raw));
	for (int &e : raw) {
		e = (e==mne?1:0);
	}

	return raw;
}


#ifdef BALBIT
signed main(){
// 	vector<int> yay = find_reachable({0, 1, 1, 2, 2, 1, 2},
// {0, 0, 1, 1, 2, 3, 3, 4, 4, 5},
// {1, 2, 2, 3, 3, 4, 5, 5, 6, 6},
// {0, 0, 1, 0, 0, 1, 2, 0, 2, 1});
	vector<int> yay = find_reachable({0, 0, 0}, {0}, {1}, {0});
	for (int t : yay) bug(t);
}
#endif

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56660 KB Output is correct
2 Correct 31 ms 56632 KB Output is correct
3 Correct 30 ms 56660 KB Output is correct
4 Correct 32 ms 56696 KB Output is correct
5 Correct 35 ms 56552 KB Output is correct
6 Correct 34 ms 56600 KB Output is correct
7 Correct 29 ms 56664 KB Output is correct
8 Correct 29 ms 56728 KB Output is correct
9 Correct 30 ms 56660 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56660 KB Output is correct
2 Correct 31 ms 56632 KB Output is correct
3 Correct 30 ms 56660 KB Output is correct
4 Correct 32 ms 56696 KB Output is correct
5 Correct 35 ms 56552 KB Output is correct
6 Correct 34 ms 56600 KB Output is correct
7 Correct 29 ms 56664 KB Output is correct
8 Correct 29 ms 56728 KB Output is correct
9 Correct 30 ms 56660 KB Output is correct
10 Correct 31 ms 56776 KB Output is correct
11 Correct 31 ms 56704 KB Output is correct
12 Correct 32 ms 56708 KB Output is correct
13 Correct 30 ms 56680 KB Output is correct
14 Correct 35 ms 56552 KB Output is correct
15 Correct 30 ms 56684 KB Output is correct
16 Correct 28 ms 56608 KB Output is correct
17 Correct 28 ms 56612 KB Output is correct
18 Correct 29 ms 56660 KB Output is correct
19 Correct 28 ms 56668 KB Output is correct
20 Correct 28 ms 56632 KB Output is correct
21 Correct 30 ms 56832 KB Output is correct
22 Correct 29 ms 56660 KB Output is correct
23 Correct 29 ms 56660 KB Output is correct
24 Correct 38 ms 56736 KB Output is correct
25 Correct 32 ms 56768 KB Output is correct
26 Correct 31 ms 56728 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56660 KB Output is correct
2 Correct 31 ms 56632 KB Output is correct
3 Correct 30 ms 56660 KB Output is correct
4 Correct 32 ms 56696 KB Output is correct
5 Correct 35 ms 56552 KB Output is correct
6 Correct 34 ms 56600 KB Output is correct
7 Correct 29 ms 56664 KB Output is correct
8 Correct 29 ms 56728 KB Output is correct
9 Correct 30 ms 56660 KB Output is correct
10 Correct 31 ms 56776 KB Output is correct
11 Correct 31 ms 56704 KB Output is correct
12 Correct 32 ms 56708 KB Output is correct
13 Correct 30 ms 56680 KB Output is correct
14 Correct 35 ms 56552 KB Output is correct
15 Correct 30 ms 56684 KB Output is correct
16 Correct 28 ms 56608 KB Output is correct
17 Correct 28 ms 56612 KB Output is correct
18 Correct 29 ms 56660 KB Output is correct
19 Correct 28 ms 56668 KB Output is correct
20 Correct 28 ms 56632 KB Output is correct
21 Correct 30 ms 56832 KB Output is correct
22 Correct 29 ms 56660 KB Output is correct
23 Correct 29 ms 56660 KB Output is correct
24 Correct 38 ms 56736 KB Output is correct
25 Correct 32 ms 56768 KB Output is correct
26 Correct 31 ms 56728 KB Output is correct
27 Correct 31 ms 57760 KB Output is correct
28 Correct 32 ms 57776 KB Output is correct
29 Correct 33 ms 57720 KB Output is correct
30 Correct 32 ms 57152 KB Output is correct
31 Correct 32 ms 57032 KB Output is correct
32 Correct 30 ms 56736 KB Output is correct
33 Correct 31 ms 57208 KB Output is correct
34 Correct 32 ms 57192 KB Output is correct
35 Correct 38 ms 57056 KB Output is correct
36 Correct 39 ms 57760 KB Output is correct
37 Correct 32 ms 57700 KB Output is correct
38 Correct 37 ms 57952 KB Output is correct
39 Correct 33 ms 57964 KB Output is correct
40 Correct 30 ms 57304 KB Output is correct
41 Correct 38 ms 57364 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56660 KB Output is correct
2 Correct 31 ms 56632 KB Output is correct
3 Correct 30 ms 56660 KB Output is correct
4 Correct 32 ms 56696 KB Output is correct
5 Correct 35 ms 56552 KB Output is correct
6 Correct 34 ms 56600 KB Output is correct
7 Correct 29 ms 56664 KB Output is correct
8 Correct 29 ms 56728 KB Output is correct
9 Correct 30 ms 56660 KB Output is correct
10 Correct 752 ms 143968 KB Output is correct
11 Correct 832 ms 224428 KB Output is correct
12 Correct 192 ms 89552 KB Output is correct
13 Correct 876 ms 227020 KB Output is correct
14 Correct 382 ms 223240 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56660 KB Output is correct
2 Correct 31 ms 56632 KB Output is correct
3 Correct 30 ms 56660 KB Output is correct
4 Correct 32 ms 56696 KB Output is correct
5 Correct 35 ms 56552 KB Output is correct
6 Correct 34 ms 56600 KB Output is correct
7 Correct 29 ms 56664 KB Output is correct
8 Correct 29 ms 56728 KB Output is correct
9 Correct 30 ms 56660 KB Output is correct
10 Correct 31 ms 56776 KB Output is correct
11 Correct 31 ms 56704 KB Output is correct
12 Correct 32 ms 56708 KB Output is correct
13 Correct 30 ms 56680 KB Output is correct
14 Correct 35 ms 56552 KB Output is correct
15 Correct 30 ms 56684 KB Output is correct
16 Correct 28 ms 56608 KB Output is correct
17 Correct 28 ms 56612 KB Output is correct
18 Correct 29 ms 56660 KB Output is correct
19 Correct 28 ms 56668 KB Output is correct
20 Correct 28 ms 56632 KB Output is correct
21 Correct 30 ms 56832 KB Output is correct
22 Correct 29 ms 56660 KB Output is correct
23 Correct 29 ms 56660 KB Output is correct
24 Correct 38 ms 56736 KB Output is correct
25 Correct 32 ms 56768 KB Output is correct
26 Correct 31 ms 56728 KB Output is correct
27 Correct 31 ms 57760 KB Output is correct
28 Correct 32 ms 57776 KB Output is correct
29 Correct 33 ms 57720 KB Output is correct
30 Correct 32 ms 57152 KB Output is correct
31 Correct 32 ms 57032 KB Output is correct
32 Correct 30 ms 56736 KB Output is correct
33 Correct 31 ms 57208 KB Output is correct
34 Correct 32 ms 57192 KB Output is correct
35 Correct 38 ms 57056 KB Output is correct
36 Correct 39 ms 57760 KB Output is correct
37 Correct 32 ms 57700 KB Output is correct
38 Correct 37 ms 57952 KB Output is correct
39 Correct 33 ms 57964 KB Output is correct
40 Correct 30 ms 57304 KB Output is correct
41 Correct 38 ms 57364 KB Output is correct
42 Correct 752 ms 143968 KB Output is correct
43 Correct 832 ms 224428 KB Output is correct
44 Correct 192 ms 89552 KB Output is correct
45 Correct 876 ms 227020 KB Output is correct
46 Correct 382 ms 223240 KB Output is correct
47 Correct 29 ms 56660 KB Output is correct
48 Correct 30 ms 56640 KB Output is correct
49 Correct 34 ms 56664 KB Output is correct
50 Correct 376 ms 220916 KB Output is correct
51 Correct 449 ms 220112 KB Output is correct
52 Correct 463 ms 167928 KB Output is correct
53 Correct 478 ms 167928 KB Output is correct
54 Correct 509 ms 168024 KB Output is correct
55 Correct 733 ms 146120 KB Output is correct
56 Correct 551 ms 204024 KB Output is correct
57 Correct 373 ms 180188 KB Output is correct
58 Correct 606 ms 247528 KB Output is correct
59 Correct 1399 ms 209100 KB Output is correct
60 Correct 708 ms 194884 KB Output is correct
61 Correct 1312 ms 206108 KB Output is correct
62 Correct 1130 ms 165812 KB Output is correct
63 Correct 471 ms 179712 KB Output is correct
64 Correct 39 ms 59472 KB Output is correct
65 Correct 38 ms 59516 KB Output is correct
66 Correct 1032 ms 165476 KB Output is correct
67 Correct 69 ms 73564 KB Output is correct
68 Correct 99 ms 84588 KB Output is correct
69 Correct 1297 ms 209580 KB Output is correct
70 Correct 153 ms 112260 KB Output is correct
71 Correct 402 ms 223012 KB Output is correct
72 Correct 1336 ms 210068 KB Output is correct
73 Correct 1016 ms 165904 KB Output is correct