oj.uz

Submission #660360

# Submission time Handle Problem Language Result Execution time Memory
660360 2022-11-21T17:45:54 Z rafatoa Factories (JOI14_factories) C++17
100 / 100
 6835 ms 318808 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
 
#define F first
// #define S second
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vpi vector<pi>
#define vb vector<bool>
#define vvb vector<vb>
#define pb push_back
#define ppb pop_back
#define read(a) for(auto &x:a) cin >> x;
#define print(a) for(auto x:a) cout << x << " "; cout << "\n";
#define vc vector<char>
#define vvc vector<vc>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
#define double ld
// #define int long long
const long long INF = 4e18;
 
const int N = 5e5+1;
 
int n;
vpi adjc[N];
unordered_set<int> adj[N];
int st[2*N][21];
long long d[N], dc[N], sub[N], par[N], best[N], vis[N], tin[N], eul[2*N];
 
int tt = 0;
 
int lg2(int x){
    return 31-__builtin_clz(x);
}
 
int cmp(int a, int b){
    return (d[a] < d[b] ? a : b);
}
 
int lca(int a, int b){
    if(tin[a] > tin[b]) swap(a, b);
    int len = tin[b]-tin[a]+1, lg = lg2(len);
    return cmp(st[tin[a]][lg], st[tin[b]-(1LL<<lg)+1][lg]);
}
 
long long dist(int a, int b){
    return dc[a]+dc[b]-2*dc[lca(a, b)];
}
 
void build(){
    int time = 0;
    function<void(int, int)> dfs0 = [&](int s, int e){
        tin[s] = time;
        eul[time++] = s;
        for(auto [u, c]:adjc[s]){
            if(u == e) continue;
            d[u] = d[s]+1;
            dc[u] = dc[s]+c;
            dfs0(u, s);
            eul[time++] = s;
        }
    };
    dfs0(1, 0);
 
    for(int i=0; i<2*n-1; i++) st[i][0] = eul[i];
    for(int j=1; j<=20; j++)
    for(int i=0; i+(1LL<<j)-1<2*n-1; i++)
        st[i][j] = cmp(st[i][j-1], st[i+(1LL<<(j-1))][j-1]);
 
    //START_CENTROID
 
    function<void(int, int)> dfs_sub = [&](int s, int e){
        sub[s] = 1;
        for(auto u:adj[s]){
            if(u == e) continue;
            dfs_sub(u, s);
            sub[s] += sub[u];
        }
    };
 
    function<int(int, int, int)> centroid = [&](int s, int e, int sz){
        for(auto u:adj[s])
            if(u != e && sub[u] > sz/2) return centroid(u, s, sz);
        return s;
    };
 
    function<void(int, int)> decompose = [&](int s, int p){
        dfs_sub(s, 0);
        int C = centroid(s, 0, sub[s]);
        par[C] = p;
 
        for(auto u:adj[C]){
            adj[u].erase(C);
            decompose(u, C);
        }
        adj[C].clear();
    };
    decompose(1, -1);
 
    //END_CENTROID
}
 
void Init(int N, int A[], int B[], int D[]){
    n = N;
    for(int i=0; i<n-1; i++){
        adjc[A[i]+1].pb({B[i]+1, D[i]});
        adjc[B[i]+1].pb({A[i]+1, D[i]});
        adj[A[i]+1].insert(B[i]+1);
        adj[B[i]+1].insert(A[i]+1);
    }
 
    build();
}
 
long long Query(int S, int X[], int T, int Y[]){
    tt++;
    long long ans = INF;
    
    for(int i=0; i<T; i++){
        Y[i]++;
        int curr = Y[i];
        while(curr != -1){
            if(vis[curr] < tt){
                vis[curr] = tt;
                best[curr] = INF;
            }
            best[curr] = min(best[curr], dist(curr, Y[i]));
            curr = par[curr];
        }
    }
 
    for(int i=0; i<S; i++){
        X[i]++;
        int curr = X[i];
        while(curr != -1){
            if(vis[curr] < tt){
                vis[curr] = tt;
                best[curr] = INF;
            }
            ans = min(ans, best[curr]+dist(curr, X[i]));
            curr = par[curr];
        }
    }
 
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39892 KB Output is correct
2 Correct 379 ms 49700 KB Output is correct
3 Correct 554 ms 49740 KB Output is correct
4 Correct 533 ms 49772 KB Output is correct
5 Correct 566 ms 50224 KB Output is correct
6 Correct 244 ms 49768 KB Output is correct
7 Correct 547 ms 49996 KB Output is correct
8 Correct 578 ms 49776 KB Output is correct
9 Correct 624 ms 50184 KB Output is correct
10 Correct 235 ms 49756 KB Output is correct
11 Correct 537 ms 49756 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 39820 KB Output is correct
2 Correct 2896 ms 274580 KB Output is correct
3 Correct 3707 ms 278476 KB Output is correct
4 Correct 1527 ms 280796 KB Output is correct
5 Correct 5829 ms 318808 KB Output is correct
6 Correct 4665 ms 279628 KB Output is correct
7 Correct 2298 ms 95488 KB Output is correct
8 Correct 667 ms 97004 KB Output is correct
9 Correct 2130 ms 100868 KB Output is correct
10 Correct 1887 ms 96792 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39892 KB Output is correct
2 Correct 379 ms 49700 KB Output is correct
3 Correct 554 ms 49740 KB Output is correct
4 Correct 533 ms 49772 KB Output is correct
5 Correct 566 ms 50224 KB Output is correct
6 Correct 244 ms 49768 KB Output is correct
7 Correct 547 ms 49996 KB Output is correct
8 Correct 578 ms 49776 KB Output is correct
9 Correct 624 ms 50184 KB Output is correct
10 Correct 235 ms 49756 KB Output is correct
11 Correct 537 ms 49756 KB Output is correct
12 Correct 24 ms 39820 KB Output is correct
13 Correct 2896 ms 274580 KB Output is correct
14 Correct 3707 ms 278476 KB Output is correct
15 Correct 1527 ms 280796 KB Output is correct
16 Correct 5829 ms 318808 KB Output is correct
17 Correct 4665 ms 279628 KB Output is correct
18 Correct 2298 ms 95488 KB Output is correct
19 Correct 667 ms 97004 KB Output is correct
20 Correct 2130 ms 100868 KB Output is correct
21 Correct 1887 ms 96792 KB Output is correct
22 Correct 3620 ms 275984 KB Output is correct
23 Correct 3612 ms 278436 KB Output is correct
24 Correct 5006 ms 279592 KB Output is correct
25 Correct 5139 ms 283500 KB Output is correct
26 Correct 5229 ms 280036 KB Output is correct
27 Correct 6835 ms 312608 KB Output is correct
28 Correct 1690 ms 284696 KB Output is correct
29 Correct 4998 ms 279484 KB Output is correct
30 Correct 5341 ms 278564 KB Output is correct
31 Correct 5376 ms 279584 KB Output is correct
32 Correct 2416 ms 102060 KB Output is correct
33 Correct 644 ms 97456 KB Output is correct
34 Correct 1485 ms 93140 KB Output is correct
35 Correct 1556 ms 93148 KB Output is correct
36 Correct 2009 ms 93836 KB Output is correct
37 Correct 1901 ms 93880 KB Output is correct