oj.uz

Submission #821332

# Submission time Handle Problem Language Result Execution time Memory
821332 2023-08-11T09:11:58 Z Alihan_8 Factories (JOI14_factories) C++17
100 / 100
 5319 ms 363100 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
//#define int long long

template <class _T>
bool chmin(_T &x, const _T &y){
    bool flag = false;
    if ( x > y ){
        x = y; flag |= true;
    }
    return flag;
}

template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag = false;
    if ( x < y ){
        x = y; flag |= true;
    }
    return flag;
}

const long long inf = 1e15 + 1;

const int N = 5e5 + 1, K = 21, M = N * 2 + 1;

vector <pair<int,int>> g[N];

vector <int> cPar[N], have;

vector <long long> res(N, inf);

int pos[M], timer = -1, tin[N], sub[N], now;

bool vis[N];

long long dis[N], sp[K][M];

void dfs(int x, int par){
    pos[++timer] = x;
    tin[x] = timer;
    for ( auto [to, w]: g[x] ){
        if ( to != par ){
            dis[to] = dis[x] + w;
            dfs(to, x);
            pos[++timer] = x;
        }
    }
}

long long lca(int l, int r){
    int lg = __lg(r - l + 1), k = 1 << lg;
    return min(sp[lg][l], sp[lg][r + 1 - k]);
}

long long get(int u, int v){
    if ( tin[u] > tin[v] ){
        swap(u, v);
    }
    return dis[u] + dis[v] - lca(tin[u], tin[v]) * 2;
}

void calcS(int x, int par){
    sub[x] = 1;
    have.pb(x);
    for ( auto [to, w]: g[x] ){
        if ( to != par and !vis[to] ){
            calcS(to, x);
            sub[x] += sub[to];
        }
    }
}

int centroid(int x, int par){
    for ( auto [to, w]: g[x] ){
        if ( !vis[to] and to != par ){
            if ( sub[to] > now / 2 ){
                return centroid(to, x);
            }
        }
    }
    return x;
}

void decompose(int x){
    have.clear();
    calcS(x, -1);
    now = sub[x];
    auto u = centroid(x, -1);
    for ( auto &v: have ){
        cPar[v].pb(u);
    }
    vis[u] = true;
    for ( auto [to, w]: g[u] ){
        if ( !vis[to] ){
            decompose(to);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for ( int i = 0; i + 1 < N; i++ ){
        g[A[i]].pb({B[i], D[i]});
        g[B[i]].pb({A[i], D[i]});
    }
    dfs(0, -1);
    for ( int i = 0; i < M; i++ ){
        sp[0][i] = dis[pos[i]];
    }
    for ( int i = 1; i < K; i++ ){
        int k = 1 << i - 1;
        for ( int j = 0; j < M; j++ ){
            sp[i][j] = min(sp[i - 1][j], sp[i - 1][min(M - 1, j + k)]);
        }
    }
    decompose(0);
}

long long Query(int S, int X[], int T, int Y[]) {
    vector <int> C;
    for ( int u = 0; u < S; u++ ){
        for ( auto v: cPar[X[u]] ){
            chmin(res[v], get(X[u], v));
            C.pb(v);
        }
    }
    long long ans = inf;
    for ( int i = 0; i < T; i++ ){
        for ( auto u: cPar[Y[i]] ){
            chmin(ans, res[u] + get(Y[i], u));
        }
    }
    for ( auto &u: C ){
        res[u] = inf;
    }
    return ans;
}

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:116:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  116 |         int k = 1 << i - 1;
      |                      ~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 192464 KB Output is correct
2 Correct 430 ms 201320 KB Output is correct
3 Correct 499 ms 209760 KB Output is correct
4 Correct 552 ms 210092 KB Output is correct
5 Correct 565 ms 210228 KB Output is correct
6 Correct 289 ms 209496 KB Output is correct
7 Correct 492 ms 209756 KB Output is correct
8 Correct 499 ms 209792 KB Output is correct
9 Correct 572 ms 210212 KB Output is correct
10 Correct 293 ms 209492 KB Output is correct
11 Correct 489 ms 209648 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 192276 KB Output is correct
2 Correct 2204 ms 274964 KB Output is correct
3 Correct 2858 ms 312440 KB Output is correct
4 Correct 947 ms 272556 KB Output is correct
5 Correct 3941 ms 355156 KB Output is correct
6 Correct 3053 ms 314104 KB Output is correct
7 Correct 1611 ms 231492 KB Output is correct
8 Correct 473 ms 227372 KB Output is correct
9 Correct 1865 ms 238016 KB Output is correct
10 Correct 1910 ms 232932 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 192464 KB Output is correct
2 Correct 430 ms 201320 KB Output is correct
3 Correct 499 ms 209760 KB Output is correct
4 Correct 552 ms 210092 KB Output is correct
5 Correct 565 ms 210228 KB Output is correct
6 Correct 289 ms 209496 KB Output is correct
7 Correct 492 ms 209756 KB Output is correct
8 Correct 499 ms 209792 KB Output is correct
9 Correct 572 ms 210212 KB Output is correct
10 Correct 293 ms 209492 KB Output is correct
11 Correct 489 ms 209648 KB Output is correct
12 Correct 92 ms 192276 KB Output is correct
13 Correct 2204 ms 274964 KB Output is correct
14 Correct 2858 ms 312440 KB Output is correct
15 Correct 947 ms 272556 KB Output is correct
16 Correct 3941 ms 355156 KB Output is correct
17 Correct 3053 ms 314104 KB Output is correct
18 Correct 1611 ms 231492 KB Output is correct
19 Correct 473 ms 227372 KB Output is correct
20 Correct 1865 ms 238016 KB Output is correct
21 Correct 1910 ms 232932 KB Output is correct
22 Correct 3085 ms 304016 KB Output is correct
23 Correct 3338 ms 309512 KB Output is correct
24 Correct 4289 ms 327372 KB Output is correct
25 Correct 4164 ms 329328 KB Output is correct
26 Correct 4113 ms 320796 KB Output is correct
27 Correct 5319 ms 363100 KB Output is correct
28 Correct 1261 ms 283744 KB Output is correct
29 Correct 4205 ms 320240 KB Output is correct
30 Correct 4176 ms 319576 KB Output is correct
31 Correct 4061 ms 320364 KB Output is correct
32 Correct 2167 ms 243816 KB Output is correct
33 Correct 703 ms 228320 KB Output is correct
34 Correct 1511 ms 228184 KB Output is correct
35 Correct 1669 ms 228320 KB Output is correct
36 Correct 1892 ms 230012 KB Output is correct
37 Correct 1849 ms 230064 KB Output is correct