oj.uz

Submission #908211

# Submission time Handle Problem Language Result Execution time Memory
908211 2024-01-16T09:35:35 Z typ_ik Factories (JOI14_factories) C++17
100 / 100
 3680 ms 159448 KB 
#include <bits/stdc++.h>
#include "factories.h"

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2")

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std; 

const int N = 5e5 + 128;
const ll INF = 1e15 + 128; 
const int LOG = 20;
vector < pair<int, int> > g[N];
int n, q;
bool was[N];
int h[N]; 
ll res[N];  

void dfs(int v, int p = -1) {
    h[v] = 1;    

    for (auto& [to, len] : g[v])
        if (to != p && !was[to])
            dfs(to, v), h[v] += h[to];
}  

int p[N];
ll dist[N][LOG];
int depth[N];

void calc(int v, int dep, ll val, int pr = -1) {
    dist[v][dep] = val;

    for (auto& [to, len] : g[v])
        if (to != pr && !was[to])
            calc(to, dep, val+len, v);
} 

int find_centroid(int v, int pr, int sz) { 
    for (auto& [to, len] : g[v])
        if (to != pr && h[to] > sz / 2 && !was[to])
            return find_centroid(to, v, sz);
    return v;
} 

void decompose(int v, int pr = -1) { 
    dfs(v); 

    int c = find_centroid(v, -1, h[v]);

    p[c] = pr;    

    if (pr != -1)
        depth[c] = depth[pr] + 1;

    calc(c, depth[c], 0);
    was[c] = true;

    for (auto& [to, len] : g[c])
        if (!was[to])
            decompose(to, c);
}

void update(int v) {
    int c = v;
    while (c != -1)
        res[c] = min(res[c], dist[v][depth[c]]), c = p[c]; 
}

void reset(int v) {
    int c = v;
    while (c != -1)
        res[c] = INF, c = p[c]; 
}

ll get(int v) {
    ll ans = INF;
    int c = v;
    while (c != -1)
        ans = min(ans, dist[v][depth[c]] + res[c]), c = p[c]; 
    return ans;
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i + 1 < n; i++) {
        int u = A[i], v = B[i], w = D[i];
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
    }
    for (int i = 0; i <= n; i++)
        res[i] = INF;
    decompose(1); 
}

long long Query(int S, int X[], int T, int Y[]) { 
    for (int i = 0; i < S; i++)
        update(X[i]);
    ll tot = INF;
    for (int i = 0; i < T; i++)
        tot = min(tot, get(Y[i]));
    for (int i = 0; i < S; i++)
        reset(X[i]); 
    return tot;
}   

// main() {
//     boost;
//     int A[] = {0, 1, 2, 2, 4, 1};
//     int B[] = {1, 2, 3, 4, 5, 6};
//     int D[] = {4, 4, 5, 6, 5, 3};
//     Init(7, A, B, D); 
//     int X[] = {0, 6};
//     int Y[] = {3, 4};
//     cout << Query(2, X, 2, Y) << '\n';
//     return 0;
// }

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 37468 KB Output is correct
2 Correct 214 ms 49104 KB Output is correct
3 Correct 353 ms 48956 KB Output is correct
4 Correct 313 ms 49096 KB Output is correct
5 Correct 249 ms 49108 KB Output is correct
6 Correct 153 ms 49108 KB Output is correct
7 Correct 252 ms 49120 KB Output is correct
8 Correct 276 ms 48980 KB Output is correct
9 Correct 264 ms 49112 KB Output is correct
10 Correct 163 ms 49128 KB Output is correct
11 Correct 232 ms 49052 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 37212 KB Output is correct
2 Correct 1370 ms 153000 KB Output is correct
3 Correct 2267 ms 152824 KB Output is correct
4 Correct 511 ms 152984 KB Output is correct
5 Correct 3306 ms 159448 KB Output is correct
6 Correct 2358 ms 143884 KB Output is correct
7 Correct 635 ms 61212 KB Output is correct
8 Correct 247 ms 63016 KB Output is correct
9 Correct 628 ms 63196 KB Output is correct
10 Correct 607 ms 61792 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 37468 KB Output is correct
2 Correct 214 ms 49104 KB Output is correct
3 Correct 353 ms 48956 KB Output is correct
4 Correct 313 ms 49096 KB Output is correct
5 Correct 249 ms 49108 KB Output is correct
6 Correct 153 ms 49108 KB Output is correct
7 Correct 252 ms 49120 KB Output is correct
8 Correct 276 ms 48980 KB Output is correct
9 Correct 264 ms 49112 KB Output is correct
10 Correct 163 ms 49128 KB Output is correct
11 Correct 232 ms 49052 KB Output is correct
12 Correct 9 ms 37212 KB Output is correct
13 Correct 1370 ms 153000 KB Output is correct
14 Correct 2267 ms 152824 KB Output is correct
15 Correct 511 ms 152984 KB Output is correct
16 Correct 3306 ms 159448 KB Output is correct
17 Correct 2358 ms 143884 KB Output is correct
18 Correct 635 ms 61212 KB Output is correct
19 Correct 247 ms 63016 KB Output is correct
20 Correct 628 ms 63196 KB Output is correct
21 Correct 607 ms 61792 KB Output is correct
22 Correct 1584 ms 141832 KB Output is correct
23 Correct 1679 ms 142764 KB Output is correct
24 Correct 2643 ms 143140 KB Output is correct
25 Correct 2661 ms 143804 KB Output is correct
26 Correct 2646 ms 143324 KB Output is correct
27 Correct 3680 ms 156220 KB Output is correct
28 Correct 613 ms 143804 KB Output is correct
29 Correct 2707 ms 142584 KB Output is correct
30 Correct 2638 ms 142932 KB Output is correct
31 Correct 3243 ms 143144 KB Output is correct
32 Correct 790 ms 63792 KB Output is correct
33 Correct 261 ms 61364 KB Output is correct
34 Correct 514 ms 60628 KB Output is correct
35 Correct 519 ms 60504 KB Output is correct
36 Correct 594 ms 62284 KB Output is correct
37 Correct 539 ms 60632 KB Output is correct