oj.uz

Submission #372926

# Submission time Handle Problem Language Result Execution time Memory
372926 2021-03-02T10:22:31 Z BartolM Factories (JOI14_factories) C++17
15 / 100
 8000 ms 112032 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const ll MAX=(ll)INF*INF;
const int MAXN=5e5+5;
const int LOG=20;

int n;
ll dist[MAXN];
int par[LOG][MAXN], dep[MAXN];
vector <pii> ls[MAXN];
ll da[MAXN], db[MAXN];

void dfs(int node, int rod, ll d) {
    par[0][node]=rod;
    dist[node]=d;
    dep[node]=dep[rod]+1;
//    printf("node: %d, dist: %lld, dep: %d, par: %d\n", node, dist[node], dep[node], rod);
    for (pii sus:ls[node]) if (sus.X!=rod) dfs(sus.X, node, d+sus.Y);
}

void build() {
    for (int i=1; i<LOG; ++i) {
        for (int j=0; j<n; ++j) {
            par[i][j]=par[i-1][par[i-1][j]];
        }
    }
}

int lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x, y);
    for (int i=LOG-1; i>=0; --i) {
        if (dep[x]-(1<<i)>=dep[y]) x=par[i][x];
    }
    if (x==y) return x;
    for (int i=LOG-1; i>=0; --i) {
        if (par[i][x]!=par[i][y]) x=par[i][x], y=par[i][y];
    }
    return par[0][x];
}

void rek(int node) {
    for (pii sus:ls[node]) {
        if (sus.X!=par[0][node]) {
            rek(sus.X);
            da[node]=min(da[node], da[sus.X]+sus.Y);
            db[node]=min(db[node], db[sus.X]+sus.Y);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for (int i=0; i<n-1; ++i) {
        ls[A[i]].pb(mp(B[i], D[i]));
        ls[B[i]].pb(mp(A[i], D[i]));
    }
    dfs(0, 0, 0);
    build();
}

long long Query(int S, int x[], int T, int y[]) {
    ll sol=MAX;
    if (S<=10 && T<=10) {
        for (int i=0; i<S; ++i) {
            for (int j=0; j<T; ++j) {
                int lc=lca(x[i], y[j]);
//                printf("x: %d, y: %d, lc: %d == %lld\n", x[i], y[j], lc);
                sol=min(sol, dist[x[i]]+dist[y[j]]-dist[lc]-dist[lc]);
            }
        }
        return sol;
    }

    for (int i=0; i<n; ++i) da[i]=db[i]=MAX;
    for (int i=0; i<S; ++i) da[x[i]]=0;
    for (int i=0; i<T; ++i) db[y[i]]=0;
    rek(0);
    for (int i=0; i<n; ++i) sol=min(sol, da[i]+db[i]);
    return sol;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12652 KB Output is correct
2 Correct 443 ms 21100 KB Output is correct
3 Correct 1026 ms 21228 KB Output is correct
4 Correct 872 ms 21100 KB Output is correct
5 Correct 491 ms 21356 KB Output is correct
6 Correct 335 ms 21100 KB Output is correct
7 Correct 1014 ms 21100 KB Output is correct
8 Correct 867 ms 21484 KB Output is correct
9 Correct 487 ms 21484 KB Output is correct
10 Correct 343 ms 21100 KB Output is correct
11 Correct 1025 ms 21296 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12396 KB Output is correct
2 Correct 2513 ms 88720 KB Output is correct
3 Correct 6590 ms 98008 KB Output is correct
4 Correct 1350 ms 96668 KB Output is correct
5 Correct 4952 ms 112032 KB Output is correct
6 Correct 4758 ms 96704 KB Output is correct
7 Execution timed out 8032 ms 50680 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12652 KB Output is correct
2 Correct 443 ms 21100 KB Output is correct
3 Correct 1026 ms 21228 KB Output is correct
4 Correct 872 ms 21100 KB Output is correct
5 Correct 491 ms 21356 KB Output is correct
6 Correct 335 ms 21100 KB Output is correct
7 Correct 1014 ms 21100 KB Output is correct
8 Correct 867 ms 21484 KB Output is correct
9 Correct 487 ms 21484 KB Output is correct
10 Correct 343 ms 21100 KB Output is correct
11 Correct 1025 ms 21296 KB Output is correct
12 Correct 11 ms 12396 KB Output is correct
13 Correct 2513 ms 88720 KB Output is correct
14 Correct 6590 ms 98008 KB Output is correct
15 Correct 1350 ms 96668 KB Output is correct
16 Correct 4952 ms 112032 KB Output is correct
17 Correct 4758 ms 96704 KB Output is correct
18 Execution timed out 8032 ms 50680 KB Time limit exceeded
19 Halted 0 ms 0 KB -