Submission #93710

#	Time	Username	Problem	Language	Result	Execution time	Memory
93710		aaa	Factories (JOI14_factories)	C++14	100 / 100	4614 ms	180308 KiB

factories

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

char lvl[500001];
int par[500001], sz[500001];
ll dist[500001][20], ans[500001];
bool done[500001];
vector<pii> adj[500001];

void dfs(int u, int p, int curlvl, ll d) {
    sz[u] = 1;
    dist[u][curlvl] = d;
    for (pii v : adj[u]) {
        if (v.first != p && !done[v.first]) {
            dfs(v.first, u, curlvl, d + v.second);
            sz[u] += sz[v.first];
        }
    }
}

int centre(int u, int p, int tot) {
    for (pii v : adj[u]) {
        if (v.first != p && !done[v.first] && sz[v.first]<<1 > tot) {
            return centre(v.first, u, tot);
        }
    }

    return u;
}

void decomp(int i, int p, int curlvl, int tot) {
    dfs(i, -1, curlvl, 0);
    int c = centre(i, -1, tot);
    dfs(c, -1, curlvl, 0);
    done[c] = true;
    lvl[c] = curlvl;
    par[c] = p;

    for (pii v : adj[c]) {
        if (v.first != p && !done[v.first]) {
             decomp(v.first, c, curlvl+1, sz[v.first]);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N-1; i++) {
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }

    for (int i = 0; i < 500000; i++)
        ans[i] = 0x3f3f3f3f3f3f3f3f;
    decomp(0, -1, 0, N);
}

long long Query(int S, int X[], int T, int Y[]) {
    ll mn = 0x3f3f3f3f3f3f3f3f;
    for (int i = 0; i < S; i++) {
        int cur = X[i];
        while(cur != -1) {
            ans[cur] = min(ans[cur], dist[X[i]][lvl[cur]]);
            cur = par[cur];
        }
    }

    for (int i = 0; i < T; i++) {
        int cur = Y[i];
        while(cur != -1) {
            mn = min(mn, dist[Y[i]][lvl[cur]] + ans[cur]);
            cur = par[cur];
        }
    }

    for (int i = 0; i < S; i++) {
        int cur = X[i];
        while(cur != -1) {
            ans[cur] = 0x3f3f3f3f3f3f3f3f;
            cur = par[cur];
        }
    }

    return mn;
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:65:57: warning: array subscript has type 'char' [-Wchar-subscripts]
             ans[cur] = min(ans[cur], dist[X[i]][lvl[cur]]);
                                                         ^
factories.cpp:73:45: warning: array subscript has type 'char' [-Wchar-subscripts]
             mn = min(mn, dist[Y[i]][lvl[cur]] + ans[cur]);
                                             ^

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67