Submission #1135124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135124		dombly	Factories (JOI14_factories)	C++20	33 / 100	4580 ms	127792 KiB

factories

#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#include "factories.h"

const int n = 5e5 + 10;
const long long inf = 1e18;
const int LOG = 19;

using namespace std;

vector<pair<int,int>>g[n];
int up[n][LOG],in[n],out[n],timer = 0,siz[n],nxt[n];
long long dist[n],ans[n];
bool was[n];

void DFS(int x,int par) {
    siz[x] = 1;
    for(auto X : g[x]) {
        if(!was[X.F] && X.F != par) {
            DFS(X.F,x);
            siz[x] += siz[X.F];
        }
    }
}

int Find(int u,int par,int q) {
    for(auto X : g[u]) {
        if(X.F != par && !was[X.F] && siz[X.F] > q / 2) return Find(X.F,u,q);
    }
    return u;
}

void Find_centroid(int u,int par) {
    DFS(u,-1);
    u = Find(u,-1,siz[u]);
    was[u] = true;
    nxt[u] = par;
    for(auto X : g[u]) {
        if(!was[X.F]) Find_centroid(X.F,u);
    }
}

bool In(int u,int v) {
    return (in[u] <= in[v] && out[u] >= out[v]);
}

int LCA(int u,int v) {
    if(In(u,v)) return u;
    if(In(v,u)) return v;
    for(int j = LOG - 1; j >= 0; j--) {
        if(up[u][j] >= 0 && !In(up[u][j],v)) u = up[u][j];
    }
    return up[u][0];
}

long long Dist(int u,int v) {
    return dist[u] + dist[v] - 2 * dist[LCA(u,v)];
}

void Add(int x) {
    int y = x;
    while(x >= 0) {
        ans[x] = min(ans[x],Dist(x,y));
        x = nxt[x];
    }
}

void Rem(int x) {
    int y = x;
    while(x >= 0) {
        ans[x] = inf;
        x = nxt[x];
    }
}

long long Get(int x) {
    long long y = x,res = inf;
    while(x >= 0) {
        res = min(res,ans[x] + Dist(x,y));
        x = nxt[x];
    }
    return res;
}

void dfs(int x,int par) {
    in[x] = ++timer;
    up[x][0] = par;
    for(int j = 1; j < LOG; j++) if(up[up[x][j - 1]][j - 1] >= 0) up[x][j] = up[up[x][j - 1]][j - 1];
    for(auto X : g[x]) {
        if(X.F != par) {
            dist[X.F] = dist[x] + X.S;
            dfs(X.F,x);
        }
    }
    out[x] = timer;
}

void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0; i < N - 1; i++) {
        g[A[i]].pb({B[i],D[i]});
        g[B[i]].pb({A[i],D[i]});
    }
    for(int i = 0; i < N; i++) for(int j = 0; j < LOG; j++) up[i][j] = -1;
    dfs(0,-1);
    Find_centroid(0,-1);
    for(int i = 0; i < N; i++) ans[i] = inf;
}

long long Query(int S, int X[], int T, int Y[]) {
    long long res = inf;
    for(int i = 0; i < S; i++) Add(X[i]);
    for(int i = 0; i < T; i++) res = min(res,Get(Y[i]));
    for(int i = 0; i < S; i++) Rem(X[i]);
    return res;
}
/*
7 3
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
3 2
0 1 3
4 6
1 1
2
5


12
3
11

*/

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