oj.uz

Submission #660389

# Submission time Handle Problem Language Result Execution time Memory
660389 2022-11-21T18:28:35 Z rafatoa Factories (JOI14_factories) C++17
100 / 100
 4326 ms 288600 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 MN = 5e5+1;
 
int n;
vpi adj[MN];
int st[2*MN][21];
long long saved[MN][21];
long long d[MN], dc[MN], sub[MN], par[MN], best[MN], vis[MN], tin[MN], eul[2*MN];
bool del[MN];
 
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]:adj[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, c]:adj[s]){
            if(u == e || del[u]) continue;
            dfs_sub(u, s);
            sub[s] += sub[u];
        }
    };
 
    function<int(int, int, int)> centroid = [&](int s, int e, int sz){
        for(auto [u, c]:adj[s])
            if(u != e && !del[u] && 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;
 
        del[C] = 1;
        for(auto [u, c]:adj[C])
            if(!del[u]) decompose(u, C);
    };
    decompose(1, -1);

    for(int i=1; i<=n; i++){
        int curr = i, c = 0;
        while(curr != -1){
            saved[i][c] = dist(i, curr);
            c++;
            curr = par[curr];
        }
    }
 
    //END_CENTROID
}
 
void Init(int N, int A[], int B[], int D[]){
    n = N;
    for(int i=0; i<n-1; i++){
        adj[A[i]+1].pb({B[i]+1, D[i]});
        adj[B[i]+1].pb({A[i]+1, D[i]});
    }

    for(int i=0; i<MN; i++)
    for(int j=0; j<=20; j++)
        saved[i][j] = -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], c = 0;
        while(curr != -1){
            if(vis[curr] < tt){
                vis[curr] = tt;
                best[curr] = INF;
            }
            best[curr] = min(best[curr], saved[Y[i]][c]);
            curr = par[curr];
            c++;
        }
    }

    for(int i=0; i<S; i++){
        X[i]++;
        int curr = X[i], c = 0;
        while(curr != -1){
            if(vis[curr] < tt){
                vis[curr] = tt;
                best[curr] = INF;
            }
            ans = min(ans, best[curr]+saved[X[i]][c]);
            curr = par[curr];
            c++;
        }
    }
 
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94796 KB Output is correct
2 Correct 302 ms 113060 KB Output is correct
3 Correct 308 ms 113036 KB Output is correct
4 Correct 291 ms 113012 KB Output is correct
5 Correct 335 ms 113432 KB Output is correct
6 Correct 243 ms 112960 KB Output is correct
7 Correct 318 ms 113060 KB Output is correct
8 Correct 298 ms 113048 KB Output is correct
9 Correct 315 ms 113508 KB Output is correct
10 Correct 206 ms 112972 KB Output is correct
11 Correct 281 ms 113012 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94492 KB Output is correct
2 Correct 1886 ms 244468 KB Output is correct
3 Correct 2652 ms 248764 KB Output is correct
4 Correct 788 ms 245100 KB Output is correct
5 Correct 3666 ms 288600 KB Output is correct
6 Correct 2732 ms 249720 KB Output is correct
7 Correct 729 ms 146932 KB Output is correct
8 Correct 389 ms 147080 KB Output is correct
9 Correct 825 ms 152176 KB Output is correct
10 Correct 734 ms 147948 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94796 KB Output is correct
2 Correct 302 ms 113060 KB Output is correct
3 Correct 308 ms 113036 KB Output is correct
4 Correct 291 ms 113012 KB Output is correct
5 Correct 335 ms 113432 KB Output is correct
6 Correct 243 ms 112960 KB Output is correct
7 Correct 318 ms 113060 KB Output is correct
8 Correct 298 ms 113048 KB Output is correct
9 Correct 315 ms 113508 KB Output is correct
10 Correct 206 ms 112972 KB Output is correct
11 Correct 281 ms 113012 KB Output is correct
12 Correct 38 ms 94492 KB Output is correct
13 Correct 1886 ms 244468 KB Output is correct
14 Correct 2652 ms 248764 KB Output is correct
15 Correct 788 ms 245100 KB Output is correct
16 Correct 3666 ms 288600 KB Output is correct
17 Correct 2732 ms 249720 KB Output is correct
18 Correct 729 ms 146932 KB Output is correct
19 Correct 389 ms 147080 KB Output is correct
20 Correct 825 ms 152176 KB Output is correct
21 Correct 734 ms 147948 KB Output is correct
22 Correct 2236 ms 246148 KB Output is correct
23 Correct 2415 ms 248256 KB Output is correct
24 Correct 3115 ms 249880 KB Output is correct
25 Correct 3146 ms 253928 KB Output is correct
26 Correct 3123 ms 250356 KB Output is correct
27 Correct 4326 ms 282540 KB Output is correct
28 Correct 1006 ms 249136 KB Output is correct
29 Correct 3419 ms 249856 KB Output is correct
30 Correct 3511 ms 248988 KB Output is correct
31 Correct 3144 ms 250292 KB Output is correct
32 Correct 854 ms 150356 KB Output is correct
33 Correct 369 ms 144192 KB Output is correct
34 Correct 585 ms 141144 KB Output is correct
35 Correct 569 ms 141148 KB Output is correct
36 Correct 734 ms 142228 KB Output is correct
37 Correct 754 ms 142028 KB Output is correct