# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

623590 | 2022-08-06T03:46:13 Z | Temmie | Keys (IOI21_keys) | C++17 | 3000 ms | 285848 KB |

#include <bits/stdc++.h> struct Dsu { std::vector <int> p; std::vector <int> size; Dsu(int s) { p.resize(s); std::iota(p.begin(), p.end(), 0); size.resize(s, 1); } int find(int v) { return v == p[v] ? v : (p[v] = find(p[v])); } void unite(int u, int v) { if ((u = find(u)) == (v = find(v))) { return; } p[u] = v; //if (size[u] > size[v]) { //p[v] = u; //} else { //p[u] = v; //} } }; struct Edge { int u, v, c; }; int n, m; std::vector <Edge> ed; std::vector <std::vector <int>> g; //std::vector <int> p; Dsu dsu(0), can(0); std::vector <int> r; std::vector <bool> last; bool go() { //can = Dsu(n); static std::vector <std::map <int, std::vector <int>>> mp(n); static std::vector <std::set <int>> st(n); bool did = false; last.assign(n, false); for (int i = 0; i < n; i++) { if (dsu.find(i) != i) { continue; } std::queue <std::pair <int, int>> q ; q.push ({ i, i }); while (q.size()) { int v = q.front().first; int p = q.front().second; q.pop(); if (p != dsu.find(p)) { continue; } if (dsu.find(v) != dsu.find(p)) { did = true; dsu.unite(p, v); continue; } //if (can.find(v) == can.find(p)) { //continue; //} //can.unite(v, p); if (last[v]) { continue; } last[v] = true; for (int x : g[v]) { int to = ed[x].u ^ ed[x].v ^ v; if (st[p].count(ed[x].c)) { q.push({ to, p }); } else { mp[p][ed[x].c].push_back(to); } } for (int x : mp[p][r[v]]) { q.push({ x, p }); } st[p].insert(r[v]); mp[p][r[v]].clear(); } } //std::vector <std::vector <int>> in(n); //for (int i = 0; i < n; i++) { //in[dsu.find(i)].push_back(i); //} //std::vector <std::vector <int>> ed_of(n); //bool did = false; //for (int j = 0; j < n; j++) { //int i = j; //if (dsu.find(i) != i || p[i] != -1) { //continue; //} //for (int v : in[i]) { //for (int x : g[v]) { //ed_of[ed[x].c].push_back(v ^ ed[x].v ^ ed[x].u); //} //} //std::vector <int> eds; //for (int x : in[i]) { //for (int y : ed_of[r[x]]) { //eds.push_back(y); //} //ed_of[r[x]].clear(); //} //for (int x : eds) { //if (dsu.find(x) == i) { //continue; //} //did = true; //if (tree.find(x) == tree.find(i)) { //int to = dsu.find(x); //while (i != to) { //int new_to = dsu.find(p[to]); //p[i] = p[to] = p[i]; //dsu.unite(to, i); //i = dsu.find(i); //to = new_to; //} //} else { //p[i] = dsu.find(x); //tree.unite(x, i); //break; //} //} //for (int v : in[i]) { //for (int x : g[v]) { //ed_of[ed[x].c].clear(); //} //} //} //std::cerr << "did ?= " << did << std::endl; return did; } std::vector <int> find_reachable(std::vector <int> _r, std::vector <int> u, std::vector <int> v, std::vector <int> c) { r = _r; n = r.size(); m = c.size(); ed.resize(m); g.resize(n); for (int i = 0; i < m; i++) { g[u[i]].push_back(i); g[v[i]].push_back(i); ed[i] = { u[i], v[i], c[i] }; } //p.resize(n, -1); dsu = Dsu(n); //tree = Dsu(n); int cnt = 0; while (go() && ++cnt < 135);// assert(++cnt < 100); //for (int i = 0; i < n; i++) std::cerr << dsu.find(i) << " \n"[i + 1 == n]; std::vector <int> ans(n, 0); for (int i = 0; i < n; i++) { ans[dsu.find(i)] += last[i];// += p[dsu.find(i)] == -1; } int res = 1 << 30; for (int x : ans) { if (x) { res = std::min(res, x); } } std::vector <int> ret(n, 1); for (int i = 0; i < n; i++) { //if (ans[dsu.find(i)] == res) { //ret[i] = 1; //} if(!last[i] || res != ans[dsu.find(i)]) { ret[i] = 0; } } return ret; }

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 212 KB | Output is correct |

2 | Correct | 0 ms | 212 KB | Output is correct |

3 | Correct | 0 ms | 212 KB | Output is correct |

4 | Correct | 0 ms | 340 KB | Output is correct |

5 | Correct | 0 ms | 212 KB | Output is correct |

6 | Correct | 0 ms | 212 KB | Output is correct |

7 | Correct | 0 ms | 212 KB | Output is correct |

8 | Correct | 1 ms | 340 KB | Output is correct |

9 | Correct | 0 ms | 340 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 212 KB | Output is correct |

2 | Correct | 0 ms | 212 KB | Output is correct |

3 | Correct | 0 ms | 212 KB | Output is correct |

4 | Correct | 0 ms | 340 KB | Output is correct |

5 | Correct | 0 ms | 212 KB | Output is correct |

6 | Correct | 0 ms | 212 KB | Output is correct |

7 | Correct | 0 ms | 212 KB | Output is correct |

8 | Correct | 1 ms | 340 KB | Output is correct |

9 | Correct | 0 ms | 340 KB | Output is correct |

10 | Correct | 1 ms | 340 KB | Output is correct |

11 | Correct | 1 ms | 340 KB | Output is correct |

12 | Correct | 1 ms | 340 KB | Output is correct |

13 | Correct | 0 ms | 212 KB | Output is correct |

14 | Correct | 0 ms | 212 KB | Output is correct |

15 | Correct | 1 ms | 300 KB | Output is correct |

16 | Correct | 0 ms | 212 KB | Output is correct |

17 | Correct | 0 ms | 212 KB | Output is correct |

18 | Correct | 1 ms | 340 KB | Output is correct |

19 | Correct | 0 ms | 212 KB | Output is correct |

20 | Correct | 0 ms | 212 KB | Output is correct |

21 | Correct | 1 ms | 340 KB | Output is correct |

22 | Correct | 0 ms | 340 KB | Output is correct |

23 | Correct | 1 ms | 340 KB | Output is correct |

24 | Correct | 1 ms | 340 KB | Output is correct |

25 | Correct | 0 ms | 340 KB | Output is correct |

26 | Correct | 1 ms | 340 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 212 KB | Output is correct |

2 | Correct | 0 ms | 212 KB | Output is correct |

3 | Correct | 0 ms | 212 KB | Output is correct |

4 | Correct | 0 ms | 340 KB | Output is correct |

5 | Correct | 0 ms | 212 KB | Output is correct |

6 | Correct | 0 ms | 212 KB | Output is correct |

7 | Correct | 0 ms | 212 KB | Output is correct |

8 | Correct | 1 ms | 340 KB | Output is correct |

9 | Correct | 0 ms | 340 KB | Output is correct |

10 | Correct | 1 ms | 340 KB | Output is correct |

11 | Correct | 1 ms | 340 KB | Output is correct |

12 | Correct | 1 ms | 340 KB | Output is correct |

13 | Correct | 0 ms | 212 KB | Output is correct |

14 | Correct | 0 ms | 212 KB | Output is correct |

15 | Correct | 1 ms | 300 KB | Output is correct |

16 | Correct | 0 ms | 212 KB | Output is correct |

17 | Correct | 0 ms | 212 KB | Output is correct |

18 | Correct | 1 ms | 340 KB | Output is correct |

19 | Correct | 0 ms | 212 KB | Output is correct |

20 | Correct | 0 ms | 212 KB | Output is correct |

21 | Correct | 1 ms | 340 KB | Output is correct |

22 | Correct | 0 ms | 340 KB | Output is correct |

23 | Correct | 1 ms | 340 KB | Output is correct |

24 | Correct | 1 ms | 340 KB | Output is correct |

25 | Correct | 0 ms | 340 KB | Output is correct |

26 | Correct | 1 ms | 340 KB | Output is correct |

27 | Correct | 3 ms | 1236 KB | Output is correct |

28 | Correct | 3 ms | 1236 KB | Output is correct |

29 | Correct | 3 ms | 1236 KB | Output is correct |

30 | Correct | 2 ms | 852 KB | Output is correct |

31 | Correct | 1 ms | 724 KB | Output is correct |

32 | Correct | 1 ms | 468 KB | Output is correct |

33 | Correct | 2 ms | 724 KB | Output is correct |

34 | Correct | 1 ms | 724 KB | Output is correct |

35 | Correct | 1 ms | 724 KB | Output is correct |

36 | Correct | 2 ms | 980 KB | Output is correct |

37 | Correct | 4 ms | 1236 KB | Output is correct |

38 | Correct | 2 ms | 1100 KB | Output is correct |

39 | Correct | 4 ms | 1492 KB | Output is correct |

40 | Correct | 2 ms | 852 KB | Output is correct |

41 | Correct | 3 ms | 1108 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 212 KB | Output is correct |

2 | Correct | 0 ms | 212 KB | Output is correct |

3 | Correct | 0 ms | 212 KB | Output is correct |

4 | Correct | 0 ms | 340 KB | Output is correct |

5 | Correct | 0 ms | 212 KB | Output is correct |

6 | Correct | 0 ms | 212 KB | Output is correct |

7 | Correct | 0 ms | 212 KB | Output is correct |

8 | Correct | 1 ms | 340 KB | Output is correct |

9 | Correct | 0 ms | 340 KB | Output is correct |

10 | Correct | 396 ms | 91056 KB | Output is correct |

11 | Correct | 355 ms | 115644 KB | Output is correct |

12 | Correct | 98 ms | 31184 KB | Output is correct |

13 | Correct | 570 ms | 149264 KB | Output is correct |

14 | Correct | 256 ms | 114180 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 212 KB | Output is correct |

2 | Correct | 0 ms | 212 KB | Output is correct |

3 | Correct | 0 ms | 212 KB | Output is correct |

4 | Correct | 0 ms | 340 KB | Output is correct |

5 | Correct | 0 ms | 212 KB | Output is correct |

6 | Correct | 0 ms | 212 KB | Output is correct |

7 | Correct | 0 ms | 212 KB | Output is correct |

8 | Correct | 1 ms | 340 KB | Output is correct |

9 | Correct | 0 ms | 340 KB | Output is correct |

10 | Correct | 1 ms | 340 KB | Output is correct |

11 | Correct | 1 ms | 340 KB | Output is correct |

12 | Correct | 1 ms | 340 KB | Output is correct |

13 | Correct | 0 ms | 212 KB | Output is correct |

14 | Correct | 0 ms | 212 KB | Output is correct |

15 | Correct | 1 ms | 300 KB | Output is correct |

16 | Correct | 0 ms | 212 KB | Output is correct |

17 | Correct | 0 ms | 212 KB | Output is correct |

18 | Correct | 1 ms | 340 KB | Output is correct |

19 | Correct | 0 ms | 212 KB | Output is correct |

20 | Correct | 0 ms | 212 KB | Output is correct |

21 | Correct | 1 ms | 340 KB | Output is correct |

22 | Correct | 0 ms | 340 KB | Output is correct |

23 | Correct | 1 ms | 340 KB | Output is correct |

24 | Correct | 1 ms | 340 KB | Output is correct |

25 | Correct | 0 ms | 340 KB | Output is correct |

26 | Correct | 1 ms | 340 KB | Output is correct |

27 | Correct | 3 ms | 1236 KB | Output is correct |

28 | Correct | 3 ms | 1236 KB | Output is correct |

29 | Correct | 3 ms | 1236 KB | Output is correct |

30 | Correct | 2 ms | 852 KB | Output is correct |

31 | Correct | 1 ms | 724 KB | Output is correct |

32 | Correct | 1 ms | 468 KB | Output is correct |

33 | Correct | 2 ms | 724 KB | Output is correct |

34 | Correct | 1 ms | 724 KB | Output is correct |

35 | Correct | 1 ms | 724 KB | Output is correct |

36 | Correct | 2 ms | 980 KB | Output is correct |

37 | Correct | 4 ms | 1236 KB | Output is correct |

38 | Correct | 2 ms | 1100 KB | Output is correct |

39 | Correct | 4 ms | 1492 KB | Output is correct |

40 | Correct | 2 ms | 852 KB | Output is correct |

41 | Correct | 3 ms | 1108 KB | Output is correct |

42 | Correct | 396 ms | 91056 KB | Output is correct |

43 | Correct | 355 ms | 115644 KB | Output is correct |

44 | Correct | 98 ms | 31184 KB | Output is correct |

45 | Correct | 570 ms | 149264 KB | Output is correct |

46 | Correct | 256 ms | 114180 KB | Output is correct |

47 | Correct | 0 ms | 212 KB | Output is correct |

48 | Correct | 0 ms | 212 KB | Output is correct |

49 | Correct | 0 ms | 212 KB | Output is correct |

50 | Correct | 229 ms | 111932 KB | Output is correct |

51 | Correct | 260 ms | 114104 KB | Output is correct |

52 | Correct | 304 ms | 103652 KB | Output is correct |

53 | Correct | 299 ms | 103636 KB | Output is correct |

54 | Correct | 305 ms | 103680 KB | Output is correct |

55 | Correct | 490 ms | 107004 KB | Output is correct |

56 | Correct | 437 ms | 139780 KB | Output is correct |

57 | Correct | 409 ms | 136612 KB | Output is correct |

58 | Correct | 677 ms | 144632 KB | Output is correct |

59 | Correct | 932 ms | 149108 KB | Output is correct |

60 | Correct | 698 ms | 141376 KB | Output is correct |

61 | Correct | 760 ms | 145580 KB | Output is correct |

62 | Execution timed out | 3102 ms | 285848 KB | Time limit exceeded |

63 | Halted | 0 ms | 0 KB | - |