oj.uz

Submission #372928

# Submission time Handle Problem Language Result Execution time Memory
372928 2021-03-02T10:30:06 Z BartolM Factories (JOI14_factories) C++17
15 / 100
 8000 ms 106248 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<=20 && T<=20) {
        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 442 ms 21100 KB Output is correct
3 Correct 1067 ms 21228 KB Output is correct
4 Correct 861 ms 21228 KB Output is correct
5 Correct 482 ms 21356 KB Output is correct
6 Correct 335 ms 21100 KB Output is correct
7 Correct 1027 ms 21344 KB Output is correct
8 Correct 874 ms 21356 KB Output is correct
9 Correct 478 ms 21356 KB Output is correct
10 Correct 332 ms 21100 KB Output is correct
11 Correct 1008 ms 21228 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 2529 ms 88556 KB Output is correct
3 Correct 6537 ms 89464 KB Output is correct
4 Correct 1288 ms 89360 KB Output is correct
5 Correct 4886 ms 106248 KB Output is correct
6 Correct 4722 ms 91032 KB Output is correct
7 Execution timed out 8074 ms 35224 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 442 ms 21100 KB Output is correct
3 Correct 1067 ms 21228 KB Output is correct
4 Correct 861 ms 21228 KB Output is correct
5 Correct 482 ms 21356 KB Output is correct
6 Correct 335 ms 21100 KB Output is correct
7 Correct 1027 ms 21344 KB Output is correct
8 Correct 874 ms 21356 KB Output is correct
9 Correct 478 ms 21356 KB Output is correct
10 Correct 332 ms 21100 KB Output is correct
11 Correct 1008 ms 21228 KB Output is correct
12 Correct 11 ms 12396 KB Output is correct
13 Correct 2529 ms 88556 KB Output is correct
14 Correct 6537 ms 89464 KB Output is correct
15 Correct 1288 ms 89360 KB Output is correct
16 Correct 4886 ms 106248 KB Output is correct
17 Correct 4722 ms 91032 KB Output is correct
18 Execution timed out 8074 ms 35224 KB Time limit exceeded
19 Halted 0 ms 0 KB -