# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
899140 | 2024-01-05T14:05:38 Z | GrindMachine | City Mapping (NOI18_citymapping) | C++17 | 73 ms | 8892 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: edi */ const int MOD = 1e9 + 7; const int N = 1e3 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; #include "citymapping.h" ll disq[N][N]; ll get_dis(ll u, ll v){ if(u == v) return 0; if(u > v) swap(u,v); if(disq[u][v] != -1) return disq[u][v]; return disq[u][v] = get_distance(u,v); } vector<pll> adj[N]; vector<bool> rem(N); vector<ll> subsiz(N); vector<ll> tin(N), tout(N); ll timer = 1; void dfs1(ll u, ll p){ tin[u] = timer++; subsiz[u] = 1; for(auto [v,w] : adj[u]){ if(v == p or rem[v]) conts; dfs1(v,u); subsiz[u] += subsiz[v]; } tout[u] = timer-1; } bool is_ances(ll u, ll v){ // is u an ances of v? return tin[u] <= tin[v] and tout[u] >= tout[v]; } ll dis_root_sub_node; void dfs2(ll u, ll p, ll des, ll d){ if(u == des){ dis_root_sub_node = d; } for(auto [v,w] : adj[u]){ if(v == p) conts; dfs2(v,u,des,d+w); } } void find_roads(int n, int q, int A[], int B[], int W[]) { memset(disq,-1,sizeof disq); vector<ll> dis(n+5); for(int i = 2; i <= n; ++i){ dis[i] = get_dis(1,i); } vector<pll> order; rep1(i,n) order.pb({dis[i],i}); sort(all(order)); ll ptr = 0; rep1(i,n-1){ ll u = order[i].ss; fill(all(rem),0); ll p = -1; while(true){ vector<ll> active; rep(j,i){ ll v = order[j].ss; if(rem[v]) conts; active.pb(v); } if(sz(active) == 1){ p = active[0]; break; } ll root = active[0]; timer = 1; dfs1(root,-1); ll nodes = sz(active); ll want = nodes/2; pll closest = {inf2,inf2}; trav(v,active){ pll px = {abs(want-subsiz[v]),v}; amin(closest,px); } ll sub_node = closest.ss; vector<ll> in_sub; trav(v,active){ if(is_ances(sub_node,v)){ in_sub.pb(v); } } dis_root_sub_node = 0; dfs2(root,-1,sub_node,0); if(dis_root_sub_node+get_dis(sub_node,u) == get_dis(root,u)){ // in sub of sub_node trav(v,active){ rem[v] = 1; } trav(v,in_sub){ rem[v] = 0; } } else{ // not in sub of v trav(v,in_sub){ rem[v] = 1; } } } ll w = dis[u]-dis[p]; A[ptr] = p; B[ptr] = u; W[ptr] = w; ptr++; adj[p].pb({u,w}), adj[u].pb({p,w}); } }
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 57 ms | 8608 KB | Correct: 8973 out of 500000 queries used. |
2 | Correct | 53 ms | 8624 KB | Correct: 9289 out of 500000 queries used. |
3 | Correct | 64 ms | 8540 KB | Correct: 9426 out of 500000 queries used. |
4 | Correct | 52 ms | 8592 KB | Correct: 9499 out of 500000 queries used. |
5 | Correct | 68 ms | 8572 KB | Correct: 9161 out of 500000 queries used. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 57 ms | 8608 KB | Correct: 8973 out of 500000 queries used. |
2 | Correct | 53 ms | 8624 KB | Correct: 9289 out of 500000 queries used. |
3 | Correct | 64 ms | 8540 KB | Correct: 9426 out of 500000 queries used. |
4 | Correct | 52 ms | 8592 KB | Correct: 9499 out of 500000 queries used. |
5 | Correct | 68 ms | 8572 KB | Correct: 9161 out of 500000 queries used. |
6 | Correct | 53 ms | 8536 KB | Correct: 8940 out of 500000 queries used. |
7 | Correct | 58 ms | 8620 KB | Correct: 9305 out of 500000 queries used. |
8 | Correct | 67 ms | 8536 KB | Correct: 9484 out of 500000 queries used. |
9 | Correct | 56 ms | 8604 KB | Correct: 9450 out of 500000 queries used. |
10 | Correct | 70 ms | 8844 KB | Correct: 9135 out of 500000 queries used. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 53 ms | 8536 KB | Correct: 8892 out of 12000 queries used. |
2 | Correct | 54 ms | 8632 KB | Correct: 8911 out of 12000 queries used. |
3 | Correct | 57 ms | 8640 KB | Correct: 8982 out of 12000 queries used. |
4 | Correct | 55 ms | 8624 KB | Correct: 8913 out of 12000 queries used. |
5 | Correct | 55 ms | 8540 KB | Correct: 8889 out of 12000 queries used. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 53 ms | 8536 KB | Correct: 8892 out of 12000 queries used. |
2 | Correct | 54 ms | 8632 KB | Correct: 8911 out of 12000 queries used. |
3 | Correct | 57 ms | 8640 KB | Correct: 8982 out of 12000 queries used. |
4 | Correct | 55 ms | 8624 KB | Correct: 8913 out of 12000 queries used. |
5 | Correct | 55 ms | 8540 KB | Correct: 8889 out of 12000 queries used. |
6 | Correct | 58 ms | 8620 KB | Correct: 8961 out of 12000 queries used. |
7 | Correct | 60 ms | 8636 KB | Correct: 8941 out of 12000 queries used. |
8 | Correct | 56 ms | 8644 KB | Correct: 8981 out of 12000 queries used. |
9 | Correct | 57 ms | 8656 KB | Correct: 8950 out of 12000 queries used. |
10 | Correct | 57 ms | 8620 KB | Correct: 8920 out of 12000 queries used. |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 57 ms | 8608 KB | Correct: 8973 out of 500000 queries used. |
2 | Correct | 53 ms | 8624 KB | Correct: 9289 out of 500000 queries used. |
3 | Correct | 64 ms | 8540 KB | Correct: 9426 out of 500000 queries used. |
4 | Correct | 52 ms | 8592 KB | Correct: 9499 out of 500000 queries used. |
5 | Correct | 68 ms | 8572 KB | Correct: 9161 out of 500000 queries used. |
6 | Correct | 53 ms | 8536 KB | Correct: 8940 out of 500000 queries used. |
7 | Correct | 58 ms | 8620 KB | Correct: 9305 out of 500000 queries used. |
8 | Correct | 67 ms | 8536 KB | Correct: 9484 out of 500000 queries used. |
9 | Correct | 56 ms | 8604 KB | Correct: 9450 out of 500000 queries used. |
10 | Correct | 70 ms | 8844 KB | Correct: 9135 out of 500000 queries used. |
11 | Correct | 53 ms | 8536 KB | Correct: 8892 out of 12000 queries used. |
12 | Correct | 54 ms | 8632 KB | Correct: 8911 out of 12000 queries used. |
13 | Correct | 57 ms | 8640 KB | Correct: 8982 out of 12000 queries used. |
14 | Correct | 55 ms | 8624 KB | Correct: 8913 out of 12000 queries used. |
15 | Correct | 55 ms | 8540 KB | Correct: 8889 out of 12000 queries used. |
16 | Correct | 58 ms | 8620 KB | Correct: 8961 out of 12000 queries used. |
17 | Correct | 60 ms | 8636 KB | Correct: 8941 out of 12000 queries used. |
18 | Correct | 56 ms | 8644 KB | Correct: 8981 out of 12000 queries used. |
19 | Correct | 57 ms | 8656 KB | Correct: 8950 out of 12000 queries used. |
20 | Correct | 57 ms | 8620 KB | Correct: 8920 out of 12000 queries used. |
21 | Correct | 58 ms | 8540 KB | Correct: 8942 out of 25000 queries used. |
22 | Correct | 56 ms | 8624 KB | Correct: 9322 out of 25000 queries used. |
23 | Correct | 56 ms | 8536 KB | Correct: 9243 out of 25000 queries used. |
24 | Correct | 57 ms | 8792 KB | Correct: 9210 out of 25000 queries used. |
25 | Correct | 66 ms | 8616 KB | Correct: 9457 out of 25000 queries used. |
26 | Correct | 65 ms | 8608 KB | Correct: 9366 out of 25000 queries used. |
27 | Correct | 66 ms | 8592 KB | Correct: 9461 out of 25000 queries used. |
28 | Correct | 68 ms | 8540 KB | Correct: 9500 out of 25000 queries used. |
29 | Correct | 66 ms | 8540 KB | Correct: 9464 out of 25000 queries used. |
30 | Correct | 68 ms | 8624 KB | Correct: 9423 out of 25000 queries used. |
31 | Correct | 55 ms | 8612 KB | Correct: 9493 out of 25000 queries used. |
32 | Correct | 60 ms | 8892 KB | Correct: 8931 out of 25000 queries used. |
33 | Correct | 52 ms | 8540 KB | Correct: 9457 out of 25000 queries used. |
34 | Correct | 54 ms | 8540 KB | Correct: 9486 out of 25000 queries used. |
35 | Correct | 52 ms | 8612 KB | Correct: 9474 out of 25000 queries used. |
36 | Correct | 59 ms | 8604 KB | Correct: 9448 out of 25000 queries used. |
37 | Correct | 53 ms | 8540 KB | Correct: 9467 out of 25000 queries used. |
38 | Correct | 55 ms | 8536 KB | Correct: 9477 out of 25000 queries used. |
39 | Correct | 55 ms | 8540 KB | Correct: 9464 out of 25000 queries used. |
40 | Correct | 54 ms | 8616 KB | Correct: 9504 out of 25000 queries used. |
41 | Correct | 54 ms | 8612 KB | Correct: 9510 out of 25000 queries used. |
42 | Correct | 53 ms | 8536 KB | Correct: 9461 out of 25000 queries used. |
43 | Correct | 56 ms | 8536 KB | Correct: 8959 out of 25000 queries used. |
44 | Correct | 52 ms | 8540 KB | Correct: 9431 out of 25000 queries used. |
45 | Correct | 53 ms | 8540 KB | Correct: 9410 out of 25000 queries used. |
46 | Correct | 53 ms | 8540 KB | Correct: 9376 out of 25000 queries used. |
47 | Correct | 55 ms | 8616 KB | Correct: 9500 out of 25000 queries used. |
48 | Correct | 52 ms | 8540 KB | Correct: 9451 out of 25000 queries used. |
49 | Correct | 55 ms | 8596 KB | Correct: 9448 out of 25000 queries used. |
50 | Correct | 52 ms | 8536 KB | Correct: 9495 out of 25000 queries used. |
51 | Correct | 54 ms | 8540 KB | Correct: 9464 out of 25000 queries used. |
52 | Correct | 55 ms | 8616 KB | Correct: 9507 out of 25000 queries used. |
53 | Correct | 53 ms | 8540 KB | Correct: 9494 out of 25000 queries used. |
54 | Correct | 57 ms | 8540 KB | Correct: 9371 out of 25000 queries used. |
55 | Correct | 60 ms | 8856 KB | Correct: 9441 out of 25000 queries used. |
56 | Correct | 56 ms | 8616 KB | Correct: 9450 out of 25000 queries used. |
57 | Correct | 55 ms | 8536 KB | Correct: 9519 out of 25000 queries used. |
58 | Correct | 54 ms | 8860 KB | Correct: 9438 out of 25000 queries used. |
59 | Correct | 51 ms | 8612 KB | Correct: 9456 out of 25000 queries used. |
60 | Correct | 73 ms | 8840 KB | Correct: 9127 out of 25000 queries used. |
61 | Correct | 66 ms | 8536 KB | Correct: 9101 out of 25000 queries used. |
62 | Correct | 66 ms | 8736 KB | Correct: 9088 out of 25000 queries used. |
63 | Correct | 67 ms | 8692 KB | Correct: 9141 out of 25000 queries used. |
64 | Correct | 68 ms | 8540 KB | Correct: 9108 out of 25000 queries used. |
65 | Correct | 58 ms | 8640 KB | Correct: 9215 out of 25000 queries used. |
66 | Correct | 67 ms | 8536 KB | Correct: 9120 out of 25000 queries used. |
67 | Correct | 57 ms | 8540 KB | Correct: 9268 out of 25000 queries used. |
68 | Correct | 58 ms | 8536 KB | Correct: 9245 out of 25000 queries used. |
69 | Correct | 59 ms | 8608 KB | Correct: 9275 out of 25000 queries used. |
70 | Correct | 57 ms | 8536 KB | Correct: 9268 out of 25000 queries used. |