oj.uz

Submission #372922

# Submission time Handle Problem Language Result Execution time Memory
372922 2021-03-02T10:09:03 Z BartolM Factories (JOI14_factories) C++17
0 / 100
 8000 ms 63384 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 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);
}

long long Query(int S, int x[], int T, int y[]) {
    for (int i=0; i<n; ++i) da[i]=db[i]=MAX;
    for (int i=0; i<S; ++i) {
        int node=x[i];
        da[node]=0;
        while (node) {
            node=par[0][node];
            da[node]=min(da[node], dist[x[i]]-dist[node]);
        }
    }
    for (int i=0; i<T; ++i) {
        int node=y[i];
        db[node]=0;
        while (node) {
            node=par[0][node];
            db[node]=min(db[node], dist[y[i]]-dist[node]);
        }
    }
    ll sol=MAX;
    for (int i=0; i<n; ++i) sol=min(sol, da[i]+db[i]);
    return sol;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12652 KB Output is correct
2 Correct 451 ms 29932 KB Output is correct
3 Correct 2306 ms 30188 KB Output is correct
4 Correct 2142 ms 30060 KB Output is correct
5 Execution timed out 8063 ms 30204 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12268 KB Output is correct
2 Execution timed out 8074 ms 63384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12652 KB Output is correct
2 Correct 451 ms 29932 KB Output is correct
3 Correct 2306 ms 30188 KB Output is correct
4 Correct 2142 ms 30060 KB Output is correct
5 Execution timed out 8063 ms 30204 KB Time limit exceeded
6 Halted 0 ms 0 KB -