# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
970836 |
2024-04-27T11:13:15 Z |
GrindMachine |
Keys (IOI21_keys) |
C++17 |
|
1106 ms |
161308 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> mp_siz(N);
vector<int> pending[N];
void merge_vectors(vector<int> &v1, vector<int> &v2){
if(sz(v1) < sz(v2)) swap(v1,v2);
trav(x,v2) v1.pb(x);
v2.clear();
}
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);
mp_siz[i]++;
}
}
}
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];
merge_vectors(pending[u],pending[v]);
merge_vectors(nodes[u],nodes[v]);
if(sz(keys[u])+mp_siz[u] < sz(keys[v])+mp_siz[v]){
swap(keys[u],keys[v]);
swap(mp[u],mp[v]);
swap(mp_siz[u],mp_siz[v]);
}
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);
mp_siz[u]--;
}
}
}
for(auto [key,adj_nodes] : mp[v]){
auto &curr = mp[u][key];
trav(w,adj_nodes){
curr.pb(w);
mp_siz[u]++;
}
if(keys[u].count(key)){
while(!curr.empty()){
int w = curr.back();
curr.pop_back();
pending[u].pb(w);
mp_siz[u]--;
}
}
}
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 |
13 ms |
54364 KB |
Output is correct |
2 |
Correct |
13 ms |
54364 KB |
Output is correct |
3 |
Correct |
13 ms |
54364 KB |
Output is correct |
4 |
Correct |
14 ms |
54364 KB |
Output is correct |
5 |
Correct |
13 ms |
54364 KB |
Output is correct |
6 |
Correct |
14 ms |
54300 KB |
Output is correct |
7 |
Correct |
13 ms |
54364 KB |
Output is correct |
8 |
Correct |
13 ms |
54364 KB |
Output is correct |
9 |
Correct |
14 ms |
54360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
54364 KB |
Output is correct |
2 |
Correct |
13 ms |
54364 KB |
Output is correct |
3 |
Correct |
13 ms |
54364 KB |
Output is correct |
4 |
Correct |
14 ms |
54364 KB |
Output is correct |
5 |
Correct |
13 ms |
54364 KB |
Output is correct |
6 |
Correct |
14 ms |
54300 KB |
Output is correct |
7 |
Correct |
13 ms |
54364 KB |
Output is correct |
8 |
Correct |
13 ms |
54364 KB |
Output is correct |
9 |
Correct |
14 ms |
54360 KB |
Output is correct |
10 |
Correct |
15 ms |
54364 KB |
Output is correct |
11 |
Correct |
14 ms |
54404 KB |
Output is correct |
12 |
Correct |
13 ms |
54364 KB |
Output is correct |
13 |
Correct |
13 ms |
54364 KB |
Output is correct |
14 |
Correct |
13 ms |
54364 KB |
Output is correct |
15 |
Correct |
14 ms |
54360 KB |
Output is correct |
16 |
Correct |
13 ms |
54200 KB |
Output is correct |
17 |
Correct |
13 ms |
54360 KB |
Output is correct |
18 |
Correct |
13 ms |
54364 KB |
Output is correct |
19 |
Correct |
13 ms |
54364 KB |
Output is correct |
20 |
Correct |
13 ms |
54336 KB |
Output is correct |
21 |
Correct |
14 ms |
54360 KB |
Output is correct |
22 |
Correct |
13 ms |
54364 KB |
Output is correct |
23 |
Correct |
13 ms |
54364 KB |
Output is correct |
24 |
Correct |
13 ms |
54364 KB |
Output is correct |
25 |
Correct |
13 ms |
54316 KB |
Output is correct |
26 |
Correct |
13 ms |
54364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
54364 KB |
Output is correct |
2 |
Correct |
13 ms |
54364 KB |
Output is correct |
3 |
Correct |
13 ms |
54364 KB |
Output is correct |
4 |
Correct |
14 ms |
54364 KB |
Output is correct |
5 |
Correct |
13 ms |
54364 KB |
Output is correct |
6 |
Correct |
14 ms |
54300 KB |
Output is correct |
7 |
Correct |
13 ms |
54364 KB |
Output is correct |
8 |
Correct |
13 ms |
54364 KB |
Output is correct |
9 |
Correct |
14 ms |
54360 KB |
Output is correct |
10 |
Correct |
15 ms |
54364 KB |
Output is correct |
11 |
Correct |
14 ms |
54404 KB |
Output is correct |
12 |
Correct |
13 ms |
54364 KB |
Output is correct |
13 |
Correct |
13 ms |
54364 KB |
Output is correct |
14 |
Correct |
13 ms |
54364 KB |
Output is correct |
15 |
Correct |
14 ms |
54360 KB |
Output is correct |
16 |
Correct |
13 ms |
54200 KB |
Output is correct |
17 |
Correct |
13 ms |
54360 KB |
Output is correct |
18 |
Correct |
13 ms |
54364 KB |
Output is correct |
19 |
Correct |
13 ms |
54364 KB |
Output is correct |
20 |
Correct |
13 ms |
54336 KB |
Output is correct |
21 |
Correct |
14 ms |
54360 KB |
Output is correct |
22 |
Correct |
13 ms |
54364 KB |
Output is correct |
23 |
Correct |
13 ms |
54364 KB |
Output is correct |
24 |
Correct |
13 ms |
54364 KB |
Output is correct |
25 |
Correct |
13 ms |
54316 KB |
Output is correct |
26 |
Correct |
13 ms |
54364 KB |
Output is correct |
27 |
Correct |
15 ms |
55132 KB |
Output is correct |
28 |
Correct |
15 ms |
55108 KB |
Output is correct |
29 |
Correct |
17 ms |
55140 KB |
Output is correct |
30 |
Correct |
14 ms |
54872 KB |
Output is correct |
31 |
Correct |
16 ms |
54580 KB |
Output is correct |
32 |
Correct |
13 ms |
54360 KB |
Output is correct |
33 |
Correct |
14 ms |
54616 KB |
Output is correct |
34 |
Correct |
14 ms |
54620 KB |
Output is correct |
35 |
Correct |
14 ms |
54620 KB |
Output is correct |
36 |
Correct |
18 ms |
54872 KB |
Output is correct |
37 |
Correct |
16 ms |
54872 KB |
Output is correct |
38 |
Correct |
16 ms |
55132 KB |
Output is correct |
39 |
Correct |
20 ms |
55384 KB |
Output is correct |
40 |
Correct |
15 ms |
54620 KB |
Output is correct |
41 |
Correct |
15 ms |
54876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
54364 KB |
Output is correct |
2 |
Correct |
13 ms |
54364 KB |
Output is correct |
3 |
Correct |
13 ms |
54364 KB |
Output is correct |
4 |
Correct |
14 ms |
54364 KB |
Output is correct |
5 |
Correct |
13 ms |
54364 KB |
Output is correct |
6 |
Correct |
14 ms |
54300 KB |
Output is correct |
7 |
Correct |
13 ms |
54364 KB |
Output is correct |
8 |
Correct |
13 ms |
54364 KB |
Output is correct |
9 |
Correct |
14 ms |
54360 KB |
Output is correct |
10 |
Correct |
309 ms |
130128 KB |
Output is correct |
11 |
Correct |
410 ms |
129492 KB |
Output is correct |
12 |
Correct |
105 ms |
74076 KB |
Output is correct |
13 |
Correct |
598 ms |
149064 KB |
Output is correct |
14 |
Correct |
241 ms |
127220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
54364 KB |
Output is correct |
2 |
Correct |
13 ms |
54364 KB |
Output is correct |
3 |
Correct |
13 ms |
54364 KB |
Output is correct |
4 |
Correct |
14 ms |
54364 KB |
Output is correct |
5 |
Correct |
13 ms |
54364 KB |
Output is correct |
6 |
Correct |
14 ms |
54300 KB |
Output is correct |
7 |
Correct |
13 ms |
54364 KB |
Output is correct |
8 |
Correct |
13 ms |
54364 KB |
Output is correct |
9 |
Correct |
14 ms |
54360 KB |
Output is correct |
10 |
Correct |
15 ms |
54364 KB |
Output is correct |
11 |
Correct |
14 ms |
54404 KB |
Output is correct |
12 |
Correct |
13 ms |
54364 KB |
Output is correct |
13 |
Correct |
13 ms |
54364 KB |
Output is correct |
14 |
Correct |
13 ms |
54364 KB |
Output is correct |
15 |
Correct |
14 ms |
54360 KB |
Output is correct |
16 |
Correct |
13 ms |
54200 KB |
Output is correct |
17 |
Correct |
13 ms |
54360 KB |
Output is correct |
18 |
Correct |
13 ms |
54364 KB |
Output is correct |
19 |
Correct |
13 ms |
54364 KB |
Output is correct |
20 |
Correct |
13 ms |
54336 KB |
Output is correct |
21 |
Correct |
14 ms |
54360 KB |
Output is correct |
22 |
Correct |
13 ms |
54364 KB |
Output is correct |
23 |
Correct |
13 ms |
54364 KB |
Output is correct |
24 |
Correct |
13 ms |
54364 KB |
Output is correct |
25 |
Correct |
13 ms |
54316 KB |
Output is correct |
26 |
Correct |
13 ms |
54364 KB |
Output is correct |
27 |
Correct |
15 ms |
55132 KB |
Output is correct |
28 |
Correct |
15 ms |
55108 KB |
Output is correct |
29 |
Correct |
17 ms |
55140 KB |
Output is correct |
30 |
Correct |
14 ms |
54872 KB |
Output is correct |
31 |
Correct |
16 ms |
54580 KB |
Output is correct |
32 |
Correct |
13 ms |
54360 KB |
Output is correct |
33 |
Correct |
14 ms |
54616 KB |
Output is correct |
34 |
Correct |
14 ms |
54620 KB |
Output is correct |
35 |
Correct |
14 ms |
54620 KB |
Output is correct |
36 |
Correct |
18 ms |
54872 KB |
Output is correct |
37 |
Correct |
16 ms |
54872 KB |
Output is correct |
38 |
Correct |
16 ms |
55132 KB |
Output is correct |
39 |
Correct |
20 ms |
55384 KB |
Output is correct |
40 |
Correct |
15 ms |
54620 KB |
Output is correct |
41 |
Correct |
15 ms |
54876 KB |
Output is correct |
42 |
Correct |
309 ms |
130128 KB |
Output is correct |
43 |
Correct |
410 ms |
129492 KB |
Output is correct |
44 |
Correct |
105 ms |
74076 KB |
Output is correct |
45 |
Correct |
598 ms |
149064 KB |
Output is correct |
46 |
Correct |
241 ms |
127220 KB |
Output is correct |
47 |
Correct |
13 ms |
54364 KB |
Output is correct |
48 |
Correct |
13 ms |
54364 KB |
Output is correct |
49 |
Correct |
14 ms |
54360 KB |
Output is correct |
50 |
Correct |
242 ms |
128624 KB |
Output is correct |
51 |
Correct |
230 ms |
126024 KB |
Output is correct |
52 |
Correct |
255 ms |
132692 KB |
Output is correct |
53 |
Correct |
254 ms |
132692 KB |
Output is correct |
54 |
Correct |
262 ms |
132576 KB |
Output is correct |
55 |
Correct |
261 ms |
139344 KB |
Output is correct |
56 |
Correct |
384 ms |
155340 KB |
Output is correct |
57 |
Correct |
284 ms |
153444 KB |
Output is correct |
58 |
Correct |
493 ms |
161308 KB |
Output is correct |
59 |
Correct |
1085 ms |
151212 KB |
Output is correct |
60 |
Correct |
326 ms |
142084 KB |
Output is correct |
61 |
Correct |
901 ms |
143960 KB |
Output is correct |
62 |
Correct |
383 ms |
135508 KB |
Output is correct |
63 |
Correct |
416 ms |
136632 KB |
Output is correct |
64 |
Correct |
17 ms |
55640 KB |
Output is correct |
65 |
Correct |
17 ms |
55644 KB |
Output is correct |
66 |
Correct |
401 ms |
135800 KB |
Output is correct |
67 |
Correct |
34 ms |
61524 KB |
Output is correct |
68 |
Correct |
58 ms |
65984 KB |
Output is correct |
69 |
Correct |
1061 ms |
151380 KB |
Output is correct |
70 |
Correct |
95 ms |
78416 KB |
Output is correct |
71 |
Correct |
233 ms |
127052 KB |
Output is correct |
72 |
Correct |
1106 ms |
151376 KB |
Output is correct |
73 |
Correct |
434 ms |
135524 KB |
Output is correct |