# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
446404 |
2021-07-21T21:00:40 Z |
LucaDantas |
Keys (IOI21_keys) |
C++17 |
|
1505 ms |
147136 KB |
#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '['; string sep = ""; for (const auto &x : v) os << sep << x, sep = ", "; return os << ']'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream &os, const set<A> &s) { os << '{'; string sep = ""; for (const auto &x : s) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const map<A, B> &m) { os << '{'; string sep = ""; for (const auto &x : m) os << sep << x.first << " -> " << x.second, sep = ", "; return os << '}'; }
void debug() { cerr << endl; }
template<typename Ini, typename... Fim> void debug(Ini I, Fim... F) { cerr << I; if(sizeof...(F)) cerr << ", "; debug(F...);}
#define db(...) cerr << "DEBUG (" << #__VA_ARGS__ << ") == ", debug(__VA_ARGS__)
#define pb push_back
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(),(a).end()
constexpr int inf = 0x3f3f3f3f;
constexpr int maxn = 3e5 + 10;
struct DSU {
int pai[maxn], peso[maxn];
vector<int> validos[maxn];
set<int> cores[maxn];
map<int,vector<int>> g[maxn];
DSU() { for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1; }
int find(int x) { return pai[x] == x ? x : pai[x] = find(pai[x]); }
void join(int a, int b) {
a = find(a), b = find(b);
if(a == b) return;
if(peso[a] < peso[b]) swap(a, b);
pai[b] = a;
peso[a] += peso[b];
for(int c : cores[b]) {
cores[a].insert(c);
if(!g[a].count(c)) continue;
vector<int>& vt = g[a][c];
for(int x : vt)
validos[a].pb(x);
g[a].erase(c);
}
cores[b].clear();
for(int v : validos[b])
validos[a].push_back(v);
validos[b].clear();
for(auto it : g[b]) {
if(!cores[a].count(it.first))
for(auto k : it.second)
g[a][it.first].pb(k);
else
for(auto k : it.second)
validos[a].pb(k);
}
g[b].clear();
}
int siz(int u) { return peso[find(u)]; }
} dsu;
int ans = inf;
int vis[maxn];
bool bom[maxn];
vector<int> cm;
void dfs(int u) {
// db("entrando", u);
vis[u] = 1;
cm.push_back(u);
while(sz(dsu.validos[u])) {
int v = dsu.find(dsu.validos[u].back());
dsu.validos[u].pop_back();
if(v == u) continue;
if(vis[v] == 2) return (void)(vis[u] = 2);
if(vis[v] == 1) {
while(cm.back() != v)
dsu.join(u, cm.back()), cm.pop_back();
dsu.join(u, v);
// db("juntando", u, v, dsu.find(u));
dfs(dsu.find(u));
return;
} else {
dfs(dsu.find(v));
vis[u] = 2; // isso significa lixo
return;
}
}
ans = min(ans, dsu.peso[u]);
bom[u] = 1;
vis[u] = 2;
// db(u, dsu.peso[u]);
// assert(u == dsu.find(u));
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
vector<int> resp(r.size(), 0);
int n = (int)(r.size()), m = (int)(u.size());
for(int i = 0; i < n; i++)
dsu.cores[i] = {r[i]};
for(int i = 0; i < m; i++)
for(int rep = 0; rep < 2; rep++, swap(u[i], v[i]))
if(r[u[i]] == c[i]) dsu.validos[u[i]].pb(v[i]);
else dsu.g[u[i]][c[i]].pb(v[i]);
for(int i = 0; i < n; i++) if(!vis[dsu.find(i)]) dfs(i);
// fprintf(stderr, "SUCESSO\n");
for(int i = 0; i < n; i++)
if(bom[dsu.find(i)] && dsu.siz(i) == ans) resp[i] = 1;
return resp;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
37836 KB |
Output is correct |
2 |
Correct |
24 ms |
37992 KB |
Output is correct |
3 |
Correct |
23 ms |
37780 KB |
Output is correct |
4 |
Correct |
24 ms |
37864 KB |
Output is correct |
5 |
Correct |
24 ms |
37804 KB |
Output is correct |
6 |
Correct |
23 ms |
37804 KB |
Output is correct |
7 |
Correct |
27 ms |
37768 KB |
Output is correct |
8 |
Correct |
24 ms |
37912 KB |
Output is correct |
9 |
Correct |
24 ms |
37836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
37836 KB |
Output is correct |
2 |
Correct |
24 ms |
37992 KB |
Output is correct |
3 |
Correct |
23 ms |
37780 KB |
Output is correct |
4 |
Correct |
24 ms |
37864 KB |
Output is correct |
5 |
Correct |
24 ms |
37804 KB |
Output is correct |
6 |
Correct |
23 ms |
37804 KB |
Output is correct |
7 |
Correct |
27 ms |
37768 KB |
Output is correct |
8 |
Correct |
24 ms |
37912 KB |
Output is correct |
9 |
Correct |
24 ms |
37836 KB |
Output is correct |
10 |
Correct |
25 ms |
37900 KB |
Output is correct |
11 |
Correct |
24 ms |
37856 KB |
Output is correct |
12 |
Correct |
23 ms |
37936 KB |
Output is correct |
13 |
Correct |
23 ms |
37836 KB |
Output is correct |
14 |
Correct |
24 ms |
37876 KB |
Output is correct |
15 |
Correct |
24 ms |
37848 KB |
Output is correct |
16 |
Correct |
24 ms |
37836 KB |
Output is correct |
17 |
Correct |
23 ms |
37860 KB |
Output is correct |
18 |
Correct |
24 ms |
37808 KB |
Output is correct |
19 |
Correct |
24 ms |
37876 KB |
Output is correct |
20 |
Correct |
24 ms |
37976 KB |
Output is correct |
21 |
Correct |
24 ms |
37880 KB |
Output is correct |
22 |
Correct |
24 ms |
37912 KB |
Output is correct |
23 |
Correct |
22 ms |
37832 KB |
Output is correct |
24 |
Correct |
24 ms |
37836 KB |
Output is correct |
25 |
Correct |
24 ms |
37836 KB |
Output is correct |
26 |
Correct |
27 ms |
37836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
37836 KB |
Output is correct |
2 |
Correct |
24 ms |
37992 KB |
Output is correct |
3 |
Correct |
23 ms |
37780 KB |
Output is correct |
4 |
Correct |
24 ms |
37864 KB |
Output is correct |
5 |
Correct |
24 ms |
37804 KB |
Output is correct |
6 |
Correct |
23 ms |
37804 KB |
Output is correct |
7 |
Correct |
27 ms |
37768 KB |
Output is correct |
8 |
Correct |
24 ms |
37912 KB |
Output is correct |
9 |
Correct |
24 ms |
37836 KB |
Output is correct |
10 |
Correct |
25 ms |
37900 KB |
Output is correct |
11 |
Correct |
24 ms |
37856 KB |
Output is correct |
12 |
Correct |
23 ms |
37936 KB |
Output is correct |
13 |
Correct |
23 ms |
37836 KB |
Output is correct |
14 |
Correct |
24 ms |
37876 KB |
Output is correct |
15 |
Correct |
24 ms |
37848 KB |
Output is correct |
16 |
Correct |
24 ms |
37836 KB |
Output is correct |
17 |
Correct |
23 ms |
37860 KB |
Output is correct |
18 |
Correct |
24 ms |
37808 KB |
Output is correct |
19 |
Correct |
24 ms |
37876 KB |
Output is correct |
20 |
Correct |
24 ms |
37976 KB |
Output is correct |
21 |
Correct |
24 ms |
37880 KB |
Output is correct |
22 |
Correct |
24 ms |
37912 KB |
Output is correct |
23 |
Correct |
22 ms |
37832 KB |
Output is correct |
24 |
Correct |
24 ms |
37836 KB |
Output is correct |
25 |
Correct |
24 ms |
37836 KB |
Output is correct |
26 |
Correct |
27 ms |
37836 KB |
Output is correct |
27 |
Correct |
26 ms |
38396 KB |
Output is correct |
28 |
Correct |
26 ms |
38388 KB |
Output is correct |
29 |
Correct |
26 ms |
38340 KB |
Output is correct |
30 |
Correct |
25 ms |
38064 KB |
Output is correct |
31 |
Correct |
24 ms |
37972 KB |
Output is correct |
32 |
Correct |
24 ms |
37988 KB |
Output is correct |
33 |
Correct |
25 ms |
38016 KB |
Output is correct |
34 |
Correct |
25 ms |
38120 KB |
Output is correct |
35 |
Correct |
27 ms |
38148 KB |
Output is correct |
36 |
Correct |
26 ms |
38476 KB |
Output is correct |
37 |
Correct |
27 ms |
38528 KB |
Output is correct |
38 |
Correct |
26 ms |
38528 KB |
Output is correct |
39 |
Correct |
27 ms |
38476 KB |
Output is correct |
40 |
Correct |
25 ms |
38076 KB |
Output is correct |
41 |
Correct |
26 ms |
38240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
37836 KB |
Output is correct |
2 |
Correct |
24 ms |
37992 KB |
Output is correct |
3 |
Correct |
23 ms |
37780 KB |
Output is correct |
4 |
Correct |
24 ms |
37864 KB |
Output is correct |
5 |
Correct |
24 ms |
37804 KB |
Output is correct |
6 |
Correct |
23 ms |
37804 KB |
Output is correct |
7 |
Correct |
27 ms |
37768 KB |
Output is correct |
8 |
Correct |
24 ms |
37912 KB |
Output is correct |
9 |
Correct |
24 ms |
37836 KB |
Output is correct |
10 |
Correct |
684 ms |
117492 KB |
Output is correct |
11 |
Correct |
498 ms |
125528 KB |
Output is correct |
12 |
Correct |
126 ms |
52536 KB |
Output is correct |
13 |
Correct |
568 ms |
106948 KB |
Output is correct |
14 |
Correct |
270 ms |
115260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
37836 KB |
Output is correct |
2 |
Correct |
24 ms |
37992 KB |
Output is correct |
3 |
Correct |
23 ms |
37780 KB |
Output is correct |
4 |
Correct |
24 ms |
37864 KB |
Output is correct |
5 |
Correct |
24 ms |
37804 KB |
Output is correct |
6 |
Correct |
23 ms |
37804 KB |
Output is correct |
7 |
Correct |
27 ms |
37768 KB |
Output is correct |
8 |
Correct |
24 ms |
37912 KB |
Output is correct |
9 |
Correct |
24 ms |
37836 KB |
Output is correct |
10 |
Correct |
25 ms |
37900 KB |
Output is correct |
11 |
Correct |
24 ms |
37856 KB |
Output is correct |
12 |
Correct |
23 ms |
37936 KB |
Output is correct |
13 |
Correct |
23 ms |
37836 KB |
Output is correct |
14 |
Correct |
24 ms |
37876 KB |
Output is correct |
15 |
Correct |
24 ms |
37848 KB |
Output is correct |
16 |
Correct |
24 ms |
37836 KB |
Output is correct |
17 |
Correct |
23 ms |
37860 KB |
Output is correct |
18 |
Correct |
24 ms |
37808 KB |
Output is correct |
19 |
Correct |
24 ms |
37876 KB |
Output is correct |
20 |
Correct |
24 ms |
37976 KB |
Output is correct |
21 |
Correct |
24 ms |
37880 KB |
Output is correct |
22 |
Correct |
24 ms |
37912 KB |
Output is correct |
23 |
Correct |
22 ms |
37832 KB |
Output is correct |
24 |
Correct |
24 ms |
37836 KB |
Output is correct |
25 |
Correct |
24 ms |
37836 KB |
Output is correct |
26 |
Correct |
27 ms |
37836 KB |
Output is correct |
27 |
Correct |
26 ms |
38396 KB |
Output is correct |
28 |
Correct |
26 ms |
38388 KB |
Output is correct |
29 |
Correct |
26 ms |
38340 KB |
Output is correct |
30 |
Correct |
25 ms |
38064 KB |
Output is correct |
31 |
Correct |
24 ms |
37972 KB |
Output is correct |
32 |
Correct |
24 ms |
37988 KB |
Output is correct |
33 |
Correct |
25 ms |
38016 KB |
Output is correct |
34 |
Correct |
25 ms |
38120 KB |
Output is correct |
35 |
Correct |
27 ms |
38148 KB |
Output is correct |
36 |
Correct |
26 ms |
38476 KB |
Output is correct |
37 |
Correct |
27 ms |
38528 KB |
Output is correct |
38 |
Correct |
26 ms |
38528 KB |
Output is correct |
39 |
Correct |
27 ms |
38476 KB |
Output is correct |
40 |
Correct |
25 ms |
38076 KB |
Output is correct |
41 |
Correct |
26 ms |
38240 KB |
Output is correct |
42 |
Correct |
684 ms |
117492 KB |
Output is correct |
43 |
Correct |
498 ms |
125528 KB |
Output is correct |
44 |
Correct |
126 ms |
52536 KB |
Output is correct |
45 |
Correct |
568 ms |
106948 KB |
Output is correct |
46 |
Correct |
270 ms |
115260 KB |
Output is correct |
47 |
Correct |
24 ms |
37804 KB |
Output is correct |
48 |
Correct |
24 ms |
37872 KB |
Output is correct |
49 |
Correct |
23 ms |
37876 KB |
Output is correct |
50 |
Correct |
291 ms |
144548 KB |
Output is correct |
51 |
Correct |
302 ms |
147136 KB |
Output is correct |
52 |
Correct |
327 ms |
97520 KB |
Output is correct |
53 |
Correct |
334 ms |
97400 KB |
Output is correct |
54 |
Correct |
327 ms |
97548 KB |
Output is correct |
55 |
Correct |
867 ms |
125448 KB |
Output is correct |
56 |
Correct |
411 ms |
116664 KB |
Output is correct |
57 |
Correct |
326 ms |
108852 KB |
Output is correct |
58 |
Correct |
639 ms |
116044 KB |
Output is correct |
59 |
Correct |
1505 ms |
127156 KB |
Output is correct |
60 |
Correct |
483 ms |
115520 KB |
Output is correct |
61 |
Correct |
943 ms |
132312 KB |
Output is correct |
62 |
Correct |
1093 ms |
136048 KB |
Output is correct |
63 |
Correct |
328 ms |
105356 KB |
Output is correct |
64 |
Correct |
28 ms |
39192 KB |
Output is correct |
65 |
Correct |
30 ms |
39244 KB |
Output is correct |
66 |
Correct |
1084 ms |
136020 KB |
Output is correct |
67 |
Correct |
48 ms |
45604 KB |
Output is correct |
68 |
Correct |
65 ms |
50644 KB |
Output is correct |
69 |
Correct |
1381 ms |
127288 KB |
Output is correct |
70 |
Correct |
108 ms |
63548 KB |
Output is correct |
71 |
Correct |
283 ms |
116128 KB |
Output is correct |
72 |
Correct |
1399 ms |
127096 KB |
Output is correct |
73 |
Correct |
1059 ms |
135896 KB |
Output is correct |