# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
970829 |
2024-04-27T10:59:40 Z |
GrindMachine |
Keys (IOI21_keys) |
C++17 |
|
1102 ms |
167100 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
refs:
https://codeforces.com/blog/entry/92083?#comment-807712
*/
const int MOD = 1e9 + 7;
const int N = 3e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
struct DSU {
vector<int> par, rankk, siz;
DSU() {
}
DSU(int n) {
init(n);
}
void init(int n) {
par = vector<int>(n + 1);
rankk = vector<int>(n + 1);
siz = vector<int>(n + 1);
rep(i, n + 1) create(i);
}
void create(int u) {
par[u] = u;
rankk[u] = 0;
siz[u] = 1;
}
int find(int u) {
if (u == par[u]) return u;
else return par[u] = find(par[u]);
}
bool same(int u, int v) {
return find(u) == find(v);
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (rankk[u] == rankk[v]) rankk[u]++;
if (rankk[u] < rankk[v]) swap(u, v);
par[v] = u;
siz[u] += siz[v];
}
};
vector<pii> adj[N];
vector<int> node_id(N), up(N);
vector<int> siz(N);
vector<int> nodes[N];
set<int> keys[N];
map<int,vector<int>> mp[N];
vector<int> pending[N];
std::vector<int> find_reachable(std::vector<int> a, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
int n = sz(a), m = sz(U);
rep(i,m){
int u = U[i], v = V[i], w = W[i];
adj[u].pb({v,w}), adj[v].pb({u,w});
}
DSU dsu(n);
set<pii> st;
rep(i,n) st.insert({1,i});
rep(i,n){
node_id[i] = i;
up[i] = i;
siz[i] = 1;
nodes[i].pb(i);
keys[i].insert(a[i]);
for(auto [v,key] : adj[i]){
if(key == a[i]){
pending[i].pb(v);
}
else{
mp[i][key].pb(v);
}
}
}
vector<int> ans(n);
int mn_reach = inf1;
while(!st.empty()){
auto [sizu,u] = *st.begin();
if(sizu > mn_reach) break;
st.erase(st.begin());
bool done = false;
while(!pending[u].empty()){
int v = pending[u].back();
pending[u].pop_back();
v = node_id[v];
if(node_id[u] == node_id[v]) conts;
done = true;
if(!dsu.same(u,v)){
// par
up[u] = v;
dsu.merge(u,v);
}
else{
// cyc
vector<int> cyc_nodes;
while(v != u){
cyc_nodes.pb(v);
v = node_id[up[v]];
}
trav(v,cyc_nodes){
node_id[v] = u;
st.erase({siz[v],v});
siz[u] += siz[v];
trav(x,pending[v]){
pending[u].pb(x);
}
pending[v].clear();
trav(x,nodes[v]){
nodes[u].pb(x);
}
nodes[v].clear();
trav(key,keys[v]){
if(keys[u].count(key)) conts;
keys[u].insert(key);
if(mp[u].count(key)){
auto &curr = mp[u][key];
while(!curr.empty()){
int w = curr.back();
curr.pop_back();
pending[u].pb(w);
}
}
}
for(auto [key,adj_nodes] : mp[v]){
auto &curr = mp[u][key];
trav(w,adj_nodes){
curr.pb(w);
}
if(keys[u].count(key)){
while(!curr.empty()){
int w = curr.back();
curr.pop_back();
pending[u].pb(w);
}
}
}
keys[v].clear();
mp[v].clear();
}
st.insert({siz[u],u});
}
break;
}
if(!done){
if(sizu < mn_reach){
mn_reach = sizu;
}
assert(sizu == mn_reach);
trav(x,nodes[u]){
ans[x] = 1;
}
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
53084 KB |
Output is correct |
2 |
Correct |
12 ms |
53084 KB |
Output is correct |
3 |
Correct |
13 ms |
53284 KB |
Output is correct |
4 |
Correct |
13 ms |
53080 KB |
Output is correct |
5 |
Correct |
13 ms |
53292 KB |
Output is correct |
6 |
Correct |
13 ms |
53284 KB |
Output is correct |
7 |
Correct |
14 ms |
53084 KB |
Output is correct |
8 |
Correct |
14 ms |
53080 KB |
Output is correct |
9 |
Correct |
13 ms |
53288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
53084 KB |
Output is correct |
2 |
Correct |
12 ms |
53084 KB |
Output is correct |
3 |
Correct |
13 ms |
53284 KB |
Output is correct |
4 |
Correct |
13 ms |
53080 KB |
Output is correct |
5 |
Correct |
13 ms |
53292 KB |
Output is correct |
6 |
Correct |
13 ms |
53284 KB |
Output is correct |
7 |
Correct |
14 ms |
53084 KB |
Output is correct |
8 |
Correct |
14 ms |
53080 KB |
Output is correct |
9 |
Correct |
13 ms |
53288 KB |
Output is correct |
10 |
Correct |
13 ms |
53340 KB |
Output is correct |
11 |
Correct |
13 ms |
53340 KB |
Output is correct |
12 |
Correct |
13 ms |
53340 KB |
Output is correct |
13 |
Correct |
13 ms |
53080 KB |
Output is correct |
14 |
Correct |
14 ms |
53336 KB |
Output is correct |
15 |
Correct |
13 ms |
53340 KB |
Output is correct |
16 |
Correct |
13 ms |
53084 KB |
Output is correct |
17 |
Correct |
12 ms |
53224 KB |
Output is correct |
18 |
Correct |
13 ms |
53084 KB |
Output is correct |
19 |
Correct |
14 ms |
53084 KB |
Output is correct |
20 |
Correct |
13 ms |
53280 KB |
Output is correct |
21 |
Correct |
13 ms |
53080 KB |
Output is correct |
22 |
Correct |
13 ms |
53084 KB |
Output is correct |
23 |
Correct |
13 ms |
53340 KB |
Output is correct |
24 |
Correct |
14 ms |
53496 KB |
Output is correct |
25 |
Correct |
14 ms |
53336 KB |
Output is correct |
26 |
Correct |
13 ms |
53288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
53084 KB |
Output is correct |
2 |
Correct |
12 ms |
53084 KB |
Output is correct |
3 |
Correct |
13 ms |
53284 KB |
Output is correct |
4 |
Correct |
13 ms |
53080 KB |
Output is correct |
5 |
Correct |
13 ms |
53292 KB |
Output is correct |
6 |
Correct |
13 ms |
53284 KB |
Output is correct |
7 |
Correct |
14 ms |
53084 KB |
Output is correct |
8 |
Correct |
14 ms |
53080 KB |
Output is correct |
9 |
Correct |
13 ms |
53288 KB |
Output is correct |
10 |
Correct |
13 ms |
53340 KB |
Output is correct |
11 |
Correct |
13 ms |
53340 KB |
Output is correct |
12 |
Correct |
13 ms |
53340 KB |
Output is correct |
13 |
Correct |
13 ms |
53080 KB |
Output is correct |
14 |
Correct |
14 ms |
53336 KB |
Output is correct |
15 |
Correct |
13 ms |
53340 KB |
Output is correct |
16 |
Correct |
13 ms |
53084 KB |
Output is correct |
17 |
Correct |
12 ms |
53224 KB |
Output is correct |
18 |
Correct |
13 ms |
53084 KB |
Output is correct |
19 |
Correct |
14 ms |
53084 KB |
Output is correct |
20 |
Correct |
13 ms |
53280 KB |
Output is correct |
21 |
Correct |
13 ms |
53080 KB |
Output is correct |
22 |
Correct |
13 ms |
53084 KB |
Output is correct |
23 |
Correct |
13 ms |
53340 KB |
Output is correct |
24 |
Correct |
14 ms |
53496 KB |
Output is correct |
25 |
Correct |
14 ms |
53336 KB |
Output is correct |
26 |
Correct |
13 ms |
53288 KB |
Output is correct |
27 |
Correct |
14 ms |
53848 KB |
Output is correct |
28 |
Correct |
14 ms |
53852 KB |
Output is correct |
29 |
Correct |
15 ms |
53852 KB |
Output is correct |
30 |
Correct |
15 ms |
53596 KB |
Output is correct |
31 |
Correct |
14 ms |
53596 KB |
Output is correct |
32 |
Correct |
13 ms |
53288 KB |
Output is correct |
33 |
Correct |
17 ms |
53596 KB |
Output is correct |
34 |
Correct |
16 ms |
53596 KB |
Output is correct |
35 |
Correct |
13 ms |
53592 KB |
Output is correct |
36 |
Correct |
16 ms |
53852 KB |
Output is correct |
37 |
Correct |
15 ms |
53852 KB |
Output is correct |
38 |
Correct |
16 ms |
53852 KB |
Output is correct |
39 |
Correct |
15 ms |
53852 KB |
Output is correct |
40 |
Correct |
14 ms |
53596 KB |
Output is correct |
41 |
Correct |
14 ms |
53816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
53084 KB |
Output is correct |
2 |
Correct |
12 ms |
53084 KB |
Output is correct |
3 |
Correct |
13 ms |
53284 KB |
Output is correct |
4 |
Correct |
13 ms |
53080 KB |
Output is correct |
5 |
Correct |
13 ms |
53292 KB |
Output is correct |
6 |
Correct |
13 ms |
53284 KB |
Output is correct |
7 |
Correct |
14 ms |
53084 KB |
Output is correct |
8 |
Correct |
14 ms |
53080 KB |
Output is correct |
9 |
Correct |
13 ms |
53288 KB |
Output is correct |
10 |
Correct |
319 ms |
133944 KB |
Output is correct |
11 |
Correct |
385 ms |
133428 KB |
Output is correct |
12 |
Correct |
113 ms |
73868 KB |
Output is correct |
13 |
Correct |
545 ms |
152916 KB |
Output is correct |
14 |
Correct |
234 ms |
131500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
53084 KB |
Output is correct |
2 |
Correct |
12 ms |
53084 KB |
Output is correct |
3 |
Correct |
13 ms |
53284 KB |
Output is correct |
4 |
Correct |
13 ms |
53080 KB |
Output is correct |
5 |
Correct |
13 ms |
53292 KB |
Output is correct |
6 |
Correct |
13 ms |
53284 KB |
Output is correct |
7 |
Correct |
14 ms |
53084 KB |
Output is correct |
8 |
Correct |
14 ms |
53080 KB |
Output is correct |
9 |
Correct |
13 ms |
53288 KB |
Output is correct |
10 |
Correct |
13 ms |
53340 KB |
Output is correct |
11 |
Correct |
13 ms |
53340 KB |
Output is correct |
12 |
Correct |
13 ms |
53340 KB |
Output is correct |
13 |
Correct |
13 ms |
53080 KB |
Output is correct |
14 |
Correct |
14 ms |
53336 KB |
Output is correct |
15 |
Correct |
13 ms |
53340 KB |
Output is correct |
16 |
Correct |
13 ms |
53084 KB |
Output is correct |
17 |
Correct |
12 ms |
53224 KB |
Output is correct |
18 |
Correct |
13 ms |
53084 KB |
Output is correct |
19 |
Correct |
14 ms |
53084 KB |
Output is correct |
20 |
Correct |
13 ms |
53280 KB |
Output is correct |
21 |
Correct |
13 ms |
53080 KB |
Output is correct |
22 |
Correct |
13 ms |
53084 KB |
Output is correct |
23 |
Correct |
13 ms |
53340 KB |
Output is correct |
24 |
Correct |
14 ms |
53496 KB |
Output is correct |
25 |
Correct |
14 ms |
53336 KB |
Output is correct |
26 |
Correct |
13 ms |
53288 KB |
Output is correct |
27 |
Correct |
14 ms |
53848 KB |
Output is correct |
28 |
Correct |
14 ms |
53852 KB |
Output is correct |
29 |
Correct |
15 ms |
53852 KB |
Output is correct |
30 |
Correct |
15 ms |
53596 KB |
Output is correct |
31 |
Correct |
14 ms |
53596 KB |
Output is correct |
32 |
Correct |
13 ms |
53288 KB |
Output is correct |
33 |
Correct |
17 ms |
53596 KB |
Output is correct |
34 |
Correct |
16 ms |
53596 KB |
Output is correct |
35 |
Correct |
13 ms |
53592 KB |
Output is correct |
36 |
Correct |
16 ms |
53852 KB |
Output is correct |
37 |
Correct |
15 ms |
53852 KB |
Output is correct |
38 |
Correct |
16 ms |
53852 KB |
Output is correct |
39 |
Correct |
15 ms |
53852 KB |
Output is correct |
40 |
Correct |
14 ms |
53596 KB |
Output is correct |
41 |
Correct |
14 ms |
53816 KB |
Output is correct |
42 |
Correct |
319 ms |
133944 KB |
Output is correct |
43 |
Correct |
385 ms |
133428 KB |
Output is correct |
44 |
Correct |
113 ms |
73868 KB |
Output is correct |
45 |
Correct |
545 ms |
152916 KB |
Output is correct |
46 |
Correct |
234 ms |
131500 KB |
Output is correct |
47 |
Correct |
13 ms |
53080 KB |
Output is correct |
48 |
Correct |
12 ms |
53080 KB |
Output is correct |
49 |
Correct |
13 ms |
53292 KB |
Output is correct |
50 |
Correct |
245 ms |
131520 KB |
Output is correct |
51 |
Correct |
234 ms |
131996 KB |
Output is correct |
52 |
Correct |
251 ms |
136460 KB |
Output is correct |
53 |
Correct |
270 ms |
136652 KB |
Output is correct |
54 |
Correct |
253 ms |
136644 KB |
Output is correct |
55 |
Correct |
273 ms |
143996 KB |
Output is correct |
56 |
Correct |
388 ms |
161620 KB |
Output is correct |
57 |
Correct |
323 ms |
159436 KB |
Output is correct |
58 |
Correct |
451 ms |
167100 KB |
Output is correct |
59 |
Correct |
1042 ms |
156984 KB |
Output is correct |
60 |
Correct |
326 ms |
148048 KB |
Output is correct |
61 |
Correct |
934 ms |
149844 KB |
Output is correct |
62 |
Correct |
399 ms |
140768 KB |
Output is correct |
63 |
Correct |
413 ms |
141896 KB |
Output is correct |
64 |
Correct |
17 ms |
54364 KB |
Output is correct |
65 |
Correct |
16 ms |
54360 KB |
Output is correct |
66 |
Correct |
392 ms |
140752 KB |
Output is correct |
67 |
Correct |
34 ms |
60756 KB |
Output is correct |
68 |
Correct |
51 ms |
65944 KB |
Output is correct |
69 |
Correct |
1051 ms |
156988 KB |
Output is correct |
70 |
Correct |
86 ms |
78928 KB |
Output is correct |
71 |
Correct |
249 ms |
132000 KB |
Output is correct |
72 |
Correct |
1102 ms |
157328 KB |
Output is correct |
73 |
Correct |
388 ms |
140680 KB |
Output is correct |