oj.uz

Submission #372925

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

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) da[x[i]]=0;
    for (int i=0; i<T; ++i) db[y[i]]=0;
    rek(0);
    ll sol=MAX;
    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 12396 KB Output is correct
2 Correct 861 ms 20516 KB Output is correct
3 Correct 952 ms 20716 KB Output is correct
4 Correct 955 ms 20716 KB Output is correct
5 Correct 1094 ms 20972 KB Output is correct
6 Correct 556 ms 30316 KB Output is correct
7 Correct 985 ms 30316 KB Output is correct
8 Correct 967 ms 30188 KB Output is correct
9 Correct 1108 ms 30444 KB Output is correct
10 Correct 541 ms 30060 KB Output is correct
11 Correct 946 ms 30060 KB Output is correct

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12396 KB Output is correct
2 Correct 861 ms 20516 KB Output is correct
3 Correct 952 ms 20716 KB Output is correct
4 Correct 955 ms 20716 KB Output is correct
5 Correct 1094 ms 20972 KB Output is correct
6 Correct 556 ms 30316 KB Output is correct
7 Correct 985 ms 30316 KB Output is correct
8 Correct 967 ms 30188 KB Output is correct
9 Correct 1108 ms 30444 KB Output is correct
10 Correct 541 ms 30060 KB Output is correct
11 Correct 946 ms 30060 KB Output is correct
12 Correct 13 ms 12268 KB Output is correct
13 Execution timed out 8087 ms 57564 KB Time limit exceeded
14 Halted 0 ms 0 KB -