oj.uz

Submission #227847

# Submission time Handle Problem Language Result Execution time Memory
227847 2020-04-29T03:42:10 Z tri Factories (JOI14_factories) C++14
33 / 100
 8000 ms 111012 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

const int LOGN = 19;
const int MAXN = 5e5 + 100;
const ll INF = 1e15;

vector<pi> aL[MAXN];

int anc[MAXN][LOGN];
int depth[MAXN];
ll rDist[MAXN];

int N;

void dfs(int cV, int pV) {
    for (pi aE : aL[cV]) {
        int aV = aE.f;
        ll eC = aE.s;
        if (aV != pV) {
            depth[aV] = depth[cV] + 1;
            rDist[aV] = rDist[cV] + eC;
            dfs(aV, cV);
            anc[aV][0] = cV;
        }
    }
}

void prep() {
    anc[0][0] = 0;
    for (int k = 1; k < LOGN; k++) {
        for (int i = 0; i < N; i++) {
            anc[i][k] = anc[anc[i][k - 1]][k - 1];
        }
    }
}

int j(int a, int d) {
    for (int i = 0; i < LOGN; i++) {
        if (d & (1 << i)) {
            a = anc[a][i];
        }
    }
    return a;
}

int fLCA(int a, int b) {
    if (depth[a] > depth[b]) swap(a, b);

    b = j(b, depth[b] - depth[a]);

    if (a == b) return a;

    for (int i = LOGN - 1; i >= 0; i--) {
        if (anc[a][i] != anc[b][i]) {
            a = anc[a][i];
            b = anc[b][i];
        }
    }
    return anc[a][0];
}


void Init(int iN, int A[], int B[], int D[]) {
    N = iN;
    for (int i = 0; i < N; i++) {
        aL[A[i]].pb({B[i], D[i]});
        aL[B[i]].pb({A[i], D[i]});
    }
    depth[0] = rDist[0] = 0;
    dfs(0, -1);
    prep();
}

ll ans;
ll best[MAXN][2];

void dfsAll(int cV, int pV) {
    for (pi aE : aL[cV]) {
        int aV = aE.f;
        ll eC = aE.s;
        if (aV != pV) {
            dfsAll(aV, cV);
            best[cV][0] = min(best[cV][0], best[aV][0] + eC);
            best[cV][1] = min(best[cV][1], best[aV][1] + eC);
        }
        ans = min(ans, best[cV][0] + best[cV][1]);
    }
}

ll Query(int S, int X[], int T, int Y[]) {
    ans = INF;
    if (S * T >= N) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 2; j++) {
                best[i][j] = INF;
            }
        }

        for (int i = 0; i < S; i++) {
            best[X[i]][0] = 0;
        }
        for (int i = 0; i < T; i++) {
            best[Y[i]][1] = 0;
        }

        dfsAll(0, -1);
    } else {
        for (int i = 0; i < S; i++) {
            for (int j = 0; j < T; j++) {
                int lca = fLCA(X[i], Y[j]);
                ll cur = rDist[X[i]] + rDist[Y[j]] - 2 * rDist[lca];
                ans = min(ans, cur);
            }
        }
    }
    assert(ans >= 0);
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12544 KB Output is correct
2 Correct 789 ms 20984 KB Output is correct
3 Correct 2385 ms 21240 KB Output is correct
4 Correct 724 ms 21112 KB Output is correct
5 Correct 975 ms 21368 KB Output is correct
6 Correct 503 ms 21100 KB Output is correct
7 Correct 2392 ms 21228 KB Output is correct
8 Correct 715 ms 21256 KB Output is correct
9 Correct 957 ms 21496 KB Output is correct
10 Correct 500 ms 20984 KB Output is correct
11 Correct 2369 ms 21244 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12288 KB Output is correct
2 Correct 1773 ms 86652 KB Output is correct
3 Correct 3721 ms 88396 KB Output is correct
4 Correct 1183 ms 87752 KB Output is correct
5 Correct 3120 ms 111012 KB Output is correct
6 Correct 3004 ms 108408 KB Output is correct
7 Correct 4689 ms 49528 KB Output is correct
8 Correct 1410 ms 50188 KB Output is correct
9 Correct 3992 ms 53288 KB Output is correct
10 Correct 2855 ms 50920 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12544 KB Output is correct
2 Correct 789 ms 20984 KB Output is correct
3 Correct 2385 ms 21240 KB Output is correct
4 Correct 724 ms 21112 KB Output is correct
5 Correct 975 ms 21368 KB Output is correct
6 Correct 503 ms 21100 KB Output is correct
7 Correct 2392 ms 21228 KB Output is correct
8 Correct 715 ms 21256 KB Output is correct
9 Correct 957 ms 21496 KB Output is correct
10 Correct 500 ms 20984 KB Output is correct
11 Correct 2369 ms 21244 KB Output is correct
12 Correct 16 ms 12288 KB Output is correct
13 Correct 1773 ms 86652 KB Output is correct
14 Correct 3721 ms 88396 KB Output is correct
15 Correct 1183 ms 87752 KB Output is correct
16 Correct 3120 ms 111012 KB Output is correct
17 Correct 3004 ms 108408 KB Output is correct
18 Correct 4689 ms 49528 KB Output is correct
19 Correct 1410 ms 50188 KB Output is correct
20 Correct 3992 ms 53288 KB Output is correct
21 Correct 2855 ms 50920 KB Output is correct
22 Execution timed out 8048 ms 100464 KB Time limit exceeded
23 Halted 0 ms 0 KB -