Submission #169689

#	Time	Username	Problem	Language	Result	Execution time	Memory
169689		cheeheng	Factories (JOI14_factories)	C++14	15 / 100	8058 ms	204180 KiB

factories

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

typedef pair<int, int> ii;

// Anything related to centroid is here
int levelC[500005];
int subtreeSizeC[500005];
long long distC[500005][22];
int pC[500005];

// Anything related to original tree is here
vector<ii> AdjList[500005];
int p[500005][22];
int depth[500005];
long long dist[500005];

int dfs1(int u, int p, int level){
    subtreeSizeC[u] = 1;
    for(ii temp: AdjList[u]){
        int v = temp.first;
        if(levelC[v] != -1 || v == p){continue;}
        subtreeSizeC[u] += dfs1(v, u, level);
    }
    return subtreeSizeC[u];
}

int dfs2(int u, int p, int subtreeSize){
    for(ii temp: AdjList[u]){
        int v = temp.first;
        if(levelC[v] != -1){continue;}
        if(v != p && subtreeSizeC[v] > subtreeSize/2){
            // move there
            return dfs2(v, u, subtreeSize);
        }
    }
    return u; // this is the centroid
}

void build(int u, int p, int level){
    //printf("build(%d, %d, %d)\n", u, p, level);
    int subtreeSize = dfs1(u, p, level);
    int centroid = dfs2(u, p, subtreeSize);
    //if(p == -1){p = centroid;}
    pC[centroid] = p; // maybe we should allow -1
    //printf("build(%d, %d, %d): levelC[%d]=%d subtreeSize=%d\n", u, p, level, centroid, level, subtreeSize);
    levelC[centroid] = level;
    for(ii temp: AdjList[centroid]){
        int v = temp.first;
        if(levelC[v] != -1){continue;} // already assigned
        build(v, centroid, level+1);
    }
}

int lca(int a, int b){
    if(depth[a] < depth[b]){
        swap(a, b);
    }

    for(int k = 21; k >= 0; k --){
        if(p[a][k] == -1){continue;}
        if(depth[p[a][k]] >= depth[b]){
            a = p[a][k];
        }
    }
    if(a == b){return a;}
    for(int k = 21; k >= 0; k --){
        if(p[a][k] != p[b][k]){
            a = p[a][k];
            b = p[b][k];
        }
    }

    return p[a][0];
}

long long distO(int a, int b){
    int lca1 = lca(a, b);
    return dist[a] + dist[b] - 2*dist[lca1];
}

void init2(int N){
    memset(levelC, -1, sizeof(levelC));
    memset(subtreeSizeC, -1, sizeof(subtreeSizeC));
    memset(distC, -1, sizeof(distC));
    memset(pC, -1, sizeof(pC));
    build(0, -1, 0); // build(1, -1, 0) for 1-index

    /*for(int i = 0; i <= N; i ++){
        printf("levelC[%d]=%d\n", i, levelC[i]);
    }*/

    int op = 0;
    /*for(int u = 0; u <= N; u ++){
        int v = u;
        for(int k = levelC[u]; k >= 0; k --){
            op ++;
            distC[u][k] = distO(u, v);
            assert(op < 6e6);
            //printf("%d %d level=%d dist=%lld\n", u, v, k, distC[u][k]);
            v = pC[v];
        }
    }*/
    //assert(N <= 5000);
}

const long long INF = (3LL << 60);
vector<int> to_update;
bool updated[500005];
long long ans[500005][2];

long long op = 0;

void update(int u, int set1){
    int v = u;
    for(int k = levelC[u]; k >= 0; k --){
        if(distC[u][k] == -1){
             distC[u][k] = distO(u, v);
        }
        ans[v][set1] = min(ans[v][set1], distC[u][k]);
        if(!updated[v]){
            updated[v] = true;
            op ++;
            to_update.push_back(v);
        }
        v = pC[v];
    }
    
}

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

    // Rooting tree using BFS to avoid confusion in centroid decomposition...
    memset(p, -1, sizeof(p));
    memset(depth, -1, sizeof(depth));
    memset(dist, -1, sizeof(dist));
    queue<int> q;
    q.push(0);
    depth[0] = 0;
    dist[0] = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(ii v: AdjList[u]){
            if(depth[v.first] == -1){
                depth[v.first] = depth[u] + 1;
                dist[v.first] = dist[u] + v.second;
                p[v.first][0] = u;
                q.push(v.first);
            }
        }
    }

    for(int k = 1; k <= 21; k ++){
        for(int i = 0; i <= N; i ++){
            if(p[i][k-1] == -1){
                p[i][k]  = -1;
            }else{
                p[i][k] = p[p[i][k-1]][k-1];
            }
        }
    }

    init2(N);

    for(int i = 0; i <= N; i ++){
        ans[i][0] = INF;
        ans[i][1] = INF;
    }

    memset(updated, false, sizeof(updated));
}

long long Query(int S, int X[], int T, int Y[]) {
    for(int i = 0; i < S; i ++){
        update(X[i], 0);
    }

    for(int i = 0; i < T; i ++){
        update(Y[i], 1);
    }

    long long result = INF;
    for(int i: to_update){
        result = min(result, ans[i][0] + ans[i][1]);
    }

    for(int i: to_update){
        ans[i][0] = INF;
        ans[i][1] = INF;
        updated[i] = false;
    }
    to_update.clear();
    return result;
}

Compilation message (stderr)

factories.cpp: In function 'void init2(int)':
factories.cpp:94:9: warning: unused variable 'op' [-Wunused-variable]
     int op = 0;
         ^~

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