oj.uz

Submission #422423

# Submission time Handle Problem Language Result Execution time Memory
422423 2021-06-10T06:21:58 Z Hideo Factories (JOI14_factories) C++17
100 / 100
 6143 ms 341280 KB 
//#include "grader.cpp"
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
#define pi pair < int, int >

const int MN = 5e5 + 7;
const ll INF = 1e18 + 7;

ll d[MN];
int sb[MN], mx[MN], del[MN];
int n;

vector < pi > g[MN];
vector < pair < int, ll > > q[MN];

void dfs (int v, int sz, int p = 0){
    sb[v] = 1;
    mx[v] = 0;
    for (pi to : g[v]){
        if (!del[to.fr] && to.fr != p){
            dfs(to.fr, sz, v);
            sb[v] += sb[to.fr];
            mx[v] = max(mx[v], sb[to.fr]);
        }
    }
    mx[v] = max(mx[v], sz - sb[v]);
//    cout << v << ' ' << sb[v] << ' '  << mx[v] << endl;
}

int fc (int v, int sz){
    while (true){
        int nv = v;
        if (mx[v] <= sz / 2)
            break;
        for (pi to : g[v]){
            if (!del[to.fr] && mx[to.fr] < mx[v]){
                v = to.fr;
                break;
            }
        }
        if (nv == v)
            break;
    }
    return v;
}

void mark (int v, int st, ll dis = 0, int p = 0){
    q[v].pb({st, dis});
    for (pi to : g[v]){
        if (to.fr != p && !del[to.fr]){
            mark(to.fr, st, dis + to.sc, v);
        }
    }
}

void cent (int v, int sz){
    dfs(v, sz);
    v = fc(v, sz);
    mark(v, v);
    del[v] = 1;
    for (pi to : g[v]){
        if (!del[to.fr]){
            if (sb[to.fr] < sb[v])
                cent(to.fr, sb[to.fr]);
            else
                cent(to.fr, sz - sb[v]);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n - 1; i++){
        g[A[i] + 1].pb({B[i] + 1, D[i]});
        g[B[i] + 1].pb({A[i] + 1, D[i]});
    }
    cent(1, n);
    memset(d, 0x3f3f3f3f, sizeof(d));
}

long long Query(int S, int X[], int T, int Y[]){
    ll ans = INF;
    for (int i = 0; i < S; i++){
        int v = X[i] + 1;
        for (auto it : q[v]){
            d[it.fr] = min(d[it.fr], it.sc);
        }
    }
    for (int i = 0; i < T; i++){
        int v = Y[i] + 1;
        for (auto it : q[v]){
            ans = min(ans, d[it.fr] + it.sc);
        }
    }
    for (int i = 0; i < S; i++){
        int v = X[i] + 1;
        for (auto it : q[v]){
            d[it.fr] = INF;
        }
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28236 KB Output is correct
2 Correct 362 ms 40456 KB Output is correct
3 Correct 389 ms 38644 KB Output is correct
4 Correct 400 ms 38672 KB Output is correct
5 Correct 413 ms 39076 KB Output is correct
6 Correct 292 ms 37604 KB Output is correct
7 Correct 385 ms 38616 KB Output is correct
8 Correct 398 ms 38136 KB Output is correct
9 Correct 413 ms 38500 KB Output is correct
10 Correct 332 ms 37064 KB Output is correct
11 Correct 386 ms 38024 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27852 KB Output is correct
2 Correct 2783 ms 192236 KB Output is correct
3 Correct 4014 ms 262852 KB Output is correct
4 Correct 1064 ms 89744 KB Output is correct
5 Correct 5464 ms 341280 KB Output is correct
6 Correct 4338 ms 263260 KB Output is correct
7 Correct 1308 ms 77056 KB Output is correct
8 Correct 534 ms 54936 KB Output is correct
9 Correct 1511 ms 90348 KB Output is correct
10 Correct 1271 ms 78320 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28236 KB Output is correct
2 Correct 362 ms 40456 KB Output is correct
3 Correct 389 ms 38644 KB Output is correct
4 Correct 400 ms 38672 KB Output is correct
5 Correct 413 ms 39076 KB Output is correct
6 Correct 292 ms 37604 KB Output is correct
7 Correct 385 ms 38616 KB Output is correct
8 Correct 398 ms 38136 KB Output is correct
9 Correct 413 ms 38500 KB Output is correct
10 Correct 332 ms 37064 KB Output is correct
11 Correct 386 ms 38024 KB Output is correct
12 Correct 17 ms 27852 KB Output is correct
13 Correct 2783 ms 192236 KB Output is correct
14 Correct 4014 ms 262852 KB Output is correct
15 Correct 1064 ms 89744 KB Output is correct
16 Correct 5464 ms 341280 KB Output is correct
17 Correct 4338 ms 263260 KB Output is correct
18 Correct 1308 ms 77056 KB Output is correct
19 Correct 534 ms 54936 KB Output is correct
20 Correct 1511 ms 90348 KB Output is correct
21 Correct 1271 ms 78320 KB Output is correct
22 Correct 3422 ms 192044 KB Output is correct
23 Correct 3573 ms 198164 KB Output is correct
24 Correct 5001 ms 265152 KB Output is correct
25 Correct 5023 ms 269092 KB Output is correct
26 Correct 4922 ms 266268 KB Output is correct
27 Correct 6143 ms 339396 KB Output is correct
28 Correct 1537 ms 94972 KB Output is correct
29 Correct 4947 ms 265328 KB Output is correct
30 Correct 4880 ms 264796 KB Output is correct
31 Correct 4868 ms 265112 KB Output is correct
32 Correct 1638 ms 99028 KB Output is correct
33 Correct 610 ms 63364 KB Output is correct
34 Correct 1010 ms 77788 KB Output is correct
35 Correct 1032 ms 78476 KB Output is correct
36 Correct 1304 ms 83348 KB Output is correct
37 Correct 1256 ms 83588 KB Output is correct