oj.uz

Submission #473047

# Submission time Handle Problem Language Result Execution time Memory
473047 2021-09-14T20:51:55 Z ljuba Factories (JOI14_factories) C++17
100 / 100
 4859 ms 235992 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

const int mxN = 600012;

typedef long long ll;

vector<pair<int, ll>> adj[mxN];
bool vis[mxN];
int sub[mxN];

int dfsSize(int s, int p = -1) {
    sub[s] = 1;
    for(auto b : adj[s]) {
        int e = b.first;
        if(e == p || vis[e])
            continue;
        dfsSize(e, s);
        sub[s] += sub[e];
    }
    return sub[s];
}

int centroid(int s, int p, int n) {
    for(auto b : adj[s]) {
        int e = b.first;
        if(e == p || vis[e])
            continue;

        if(sub[e] > n/2)
            return centroid(e, s, n);
    }

    return s;
}

vector<ll> dist[mxN];

void dfs(int s, int p = -1) {
    ll vrednost = 0;
    for(auto b : adj[s]) {
        int e = b.first;
        if(e == p) {
            vrednost = b.second;
            break;
        }
    }
    if(p == -1) {
        dist[s].push_back(0);
    } else {
        dist[s].push_back(vrednost + dist[p].back());
    }
    for(auto b : adj[s]) {
        int e = b.first;
        if(e == p || vis[e])
            continue;
        dfs(e, s);
    }
}

int iznad[mxN];

void build(int s, int p = -1) {
    int n = dfsSize(s);
    int c = centroid(s, -1, n);

    dfs(c, -1);
    iznad[c] = p;
    vis[c] = true;

    for(auto b : adj[c]) {
        int e = b.first;
        if(vis[e])
            continue;
        build(e, c);
    }
}

ll mini[mxN];

void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0; i < N-1; ++i) {
        int u = A[i], v = B[i];
        ll w = D[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    build(0);

    for(int i = 0; i < N; ++i) reverse(dist[i].begin(), dist[i].end());

    for(int i = 0; i < N; ++i)
        mini[i] = LLONG_MAX;
}

long long Query(int S, int X[], int T, int Y[]) {
    //drzi za prve, za druge samo proveri
    ll ans = LLONG_MAX;
    for(int i = 0; i < S; ++i) {
        int trenutni = X[i];
        for(int j = trenutni, cnt = 0; j != -1; j = iznad[j], ++cnt) {
            mini[j] = min(mini[j], dist[trenutni][cnt]);
        }
    }

    for(int i = 0; i < T; ++i) {
        int trenutni = Y[i];
        for(int j = trenutni, cnt = 0; j != -1; j = iznad[j], ++cnt) {
            if(mini[j] == LLONG_MAX) {
                continue;
            }
            ans = min(ans, mini[j] + dist[trenutni][cnt]);
        }
    }

    for(int i = 0; i < S; ++i) {
        int trenutni = X[i];
        for(int j = trenutni, cnt = 0; j != -1; j = iznad[j], ++cnt) {
            mini[j] = LLONG_MAX;
        }
    }

    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28848 KB Output is correct
2 Correct 369 ms 37284 KB Output is correct
3 Correct 380 ms 37568 KB Output is correct
4 Correct 373 ms 37600 KB Output is correct
5 Correct 411 ms 37956 KB Output is correct
6 Correct 252 ms 36992 KB Output is correct
7 Correct 378 ms 37824 KB Output is correct
8 Correct 382 ms 37696 KB Output is correct
9 Correct 407 ms 37908 KB Output is correct
10 Correct 251 ms 36956 KB Output is correct
11 Correct 384 ms 37492 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28620 KB Output is correct
2 Correct 2456 ms 141812 KB Output is correct
3 Correct 3443 ms 179672 KB Output is correct
4 Correct 877 ms 88764 KB Output is correct
5 Correct 4114 ms 235992 KB Output is correct
6 Correct 3508 ms 180644 KB Output is correct
7 Correct 1104 ms 62732 KB Output is correct
8 Correct 433 ms 51088 KB Output is correct
9 Correct 1250 ms 71372 KB Output is correct
10 Correct 1124 ms 63764 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28848 KB Output is correct
2 Correct 369 ms 37284 KB Output is correct
3 Correct 380 ms 37568 KB Output is correct
4 Correct 373 ms 37600 KB Output is correct
5 Correct 411 ms 37956 KB Output is correct
6 Correct 252 ms 36992 KB Output is correct
7 Correct 378 ms 37824 KB Output is correct
8 Correct 382 ms 37696 KB Output is correct
9 Correct 407 ms 37908 KB Output is correct
10 Correct 251 ms 36956 KB Output is correct
11 Correct 384 ms 37492 KB Output is correct
12 Correct 18 ms 28620 KB Output is correct
13 Correct 2456 ms 141812 KB Output is correct
14 Correct 3443 ms 179672 KB Output is correct
15 Correct 877 ms 88764 KB Output is correct
16 Correct 4114 ms 235992 KB Output is correct
17 Correct 3508 ms 180644 KB Output is correct
18 Correct 1104 ms 62732 KB Output is correct
19 Correct 433 ms 51088 KB Output is correct
20 Correct 1250 ms 71372 KB Output is correct
21 Correct 1124 ms 63764 KB Output is correct
22 Correct 2820 ms 142504 KB Output is correct
23 Correct 2912 ms 145992 KB Output is correct
24 Correct 4155 ms 181184 KB Output is correct
25 Correct 4134 ms 184964 KB Output is correct
26 Correct 4185 ms 181748 KB Output is correct
27 Correct 4859 ms 232840 KB Output is correct
28 Correct 1080 ms 93084 KB Output is correct
29 Correct 4224 ms 181668 KB Output is correct
30 Correct 4061 ms 181020 KB Output is correct
31 Correct 4132 ms 181692 KB Output is correct
32 Correct 1285 ms 80276 KB Output is correct
33 Correct 432 ms 59332 KB Output is correct
34 Correct 821 ms 66016 KB Output is correct
35 Correct 895 ms 66420 KB Output is correct
36 Correct 1122 ms 69460 KB Output is correct
37 Correct 1145 ms 69444 KB Output is correct