Submission #398202

#	Time	Username	Problem	Language	Result	Execution time	Memory
398202		Encodeous	Factories (JOI14_factories)	C++11	100 / 100	5010 ms	311596 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
#pragma message("Compiling at: " __TIMESTAMP__ ". Executing File: " __FILE__ ". If this date is not the same as the submission date, it could be an indication that the submission was rejudged.")
#ifdef DEBUG
#pragma message("Attention, this program is running in DEBUG mode! Performance will be affected")
#else
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#endif
using namespace std;
#define ll long long
#define lp pair<ll,ll>
#define ld long double
#define ms(x, y) memset(x, 0, sizeof(x))
#define l2(x) ((x==0)? 0 :31 - __builtin_clz(x))
int fl2[3000001];
int cur = 0;
int head[500001], vnext[1000001], adj[1000001], weight[1000001];
int ett_idx = 1;
int ettd[20][2000001];
int ettd2[20][2000001];
int in[500001];
int cnt[500001];
int cqstat[500001];
bitset<500001> blocked;
int parent[500001];
ll ct_val[500001];
ll dist[500001];
int depth[500001];
ll cdist[20][500001];
int cparent[500001];
inline int func(int a, int a1, int b, int b1){
    if(a < b) return a1;
    return b1;
}
inline int lca_rmq(int l, int r){
    int sz = fl2[r - l + 1];
    return func(ettd[sz][l], ettd2[sz][l], ettd[sz][r - (1 << sz) + 1], ettd2[sz][r - (1 << sz) + 1]);
}
int req_size(int x, int p){
    if(blocked[x]) return 0;
    cnt[x] = 1;
    for(int i = head[x]; i != -1; i = vnext[i]){
        if(adj[i] != p && !blocked[x]){
            cnt[x] += req_size(adj[i], x);
        }
    }
    return cnt[x];
}
void ett(int x, int p){
    in[x] = ett_idx;
    ettd[0][ett_idx] = depth[x];
    ettd2[0][ett_idx++] = x;
    for(int i = head[x]; i != -1; i = vnext[i]){
        int v = adj[i];
        int w = weight[i];
        if(v != p){
            depth[v] = depth[x] + 1;
            dist[v] = dist[x] + w;
            ett(v, x);
            ettd[0][ett_idx] = depth[x];
            ettd2[0][ett_idx++] = x;
        }
    }
}
int find_centroid(int x, int p, int sz){
    for(int i = head[x]; i != -1; i = vnext[i]){
        if(adj[i] != p && !blocked[adj[i]] && cnt[adj[i]] > sz / 2){
            return find_centroid(adj[i], x, sz);
        }
    }
    return x;
}
int ffind_centroid(int x){
    //visited.reset();
    int sz = cnt[x];
    int v = x;
    int p = -1;

    while(true){
        bool any = false;
        for(int i = head[v]; i != -1; i = vnext[i]){
            if(adj[i] != p && !blocked[adj[i]] && cnt[adj[i]] > sz / 2){
                p = v;
                v = adj[i];
                any = true;
                break;
            }
        }
        if(!any) return v;
    }
}
void build_centroid_tree(int x, int p, int d = 0){
    req_size(x, p);
    //x = find_centroid(x, -1, cnt[x]);
    x = ffind_centroid(x);
    parent[x] = p;
    blocked[x] = true;
    for(int i = head[x]; i != -1; i = vnext[i]){
        if(!blocked[adj[i]]){
            build_centroid_tree(adj[i], x, d + 1);
        }
    }
}
inline ll lca_d(int a, int b){
    int x = in[a];
    int y = in[b];
    if(x > y) swap(x,y);
    int anc = lca_rmq(x,y);
    return dist[a] + dist[b] - 2 * dist[anc];
}
void update(int x, int qstat){
    int idx = 0;
    for(int c = x; c != -1; c = parent[c]){
        if(cdist[idx][x] == -1) cdist[idx][x] = lca_d(c, x);
        if(cqstat[c] != qstat) {
            ct_val[c] = cdist[idx][x];
            cqstat[c] = qstat;
        }
        ct_val[c] = min(ct_val[c], cdist[idx][x]);
        idx++;
    }
}
ll query(int x, int qstat){
    int q = 0;
    ll minv = 1e17;
    for(int c = x ; c != -1; c = parent[c]) {
        if(cdist[q][x] == -1) cdist[q][x] = lca_d(c, x);
        if(cqstat[c] == qstat){
            minv = min(minv, ct_val[c] + cdist[q][x]);
        }
        q++;
    }
    return minv;
}
void Init(int N, int A[], int B[], int D[]){
    fill(ct_val, ct_val + 500001, 1e17);
    fill(parent, parent + 500001, -1);
    fill(head, head + 500001, -1);
    for(int i = 0; i < 20; i++){
        fill(cdist[i], cdist[i] + 500001, -1);
    }
    for(int i = 1; i <= 3000000; i++){
        fl2[i] = l2(i);
    }
    int x = 0;
    for(int i =0 ; i < N-1; i++){
        int u = A[i];
        int v = B[i];
        adj[cur] = v; weight[cur] = D[i]; vnext[cur] = head[u]; head[u] = cur++;
        adj[cur] = u; weight[cur] = D[i]; vnext[cur] = head[v]; head[v] = cur++;
        x = A[i];
    }

    build_centroid_tree(x, -1);
    ett(x,x);
    for(int i = 1; i < fl2[ett_idx+1] + 1; i++){
        for(int j = 0; j + (1 << i) <= ett_idx+1; j++){
            if(ettd[i-1][j] < ettd[i-1][j + (1 << (i-1))]){
                ettd[i][j] = ettd[i-1][j];
                ettd2[i][j] = ettd2[i-1][j];
            }else{
                ettd[i][j] = ettd[i-1][j + (1 << (i-1))];
                ettd2[i][j] = ettd2[i-1][j + (1 << (i-1))];
            }
        }
    }
    auto start = chrono::system_clock::now();
//    for(int i = 0; i < N; i++){
//        int idx = 0;
//        for(int c = i; c != -1; c = parent[c]){
//            cdist[idx][i] = lca_d(c, i);
//            idx++;
//        }
//        cparent[i] = idx;
//    }
    auto dur = chrono::duration<double, std::milli>(chrono::system_clock::now() - start).count();
    assert(dur <= 500);
}
int curqstat = 1;
ll Query(int S, int X[], int T, int Y[]){
    curqstat++;
    for(int i = 0; i < S; i++){
        update(X[i], curqstat);
    }
    ll mind = 1e17;
    for(int i = 0; i < T; i++){
        mind = min(mind, query(Y[i], curqstat));
    }
    return mind;
}

//int main(){
//    int N, Q;
//    assert(scanf("%i %i", &N, &Q) == 2);
//    int *A = (int*)malloc(sizeof(int) * (N - 1));
//    int *B = (int*)malloc(sizeof(int) * (N - 1));
//    int *D = (int*)malloc(sizeof(int) * (N - 1));
//    for(int a = 0; a < N - 1; a++){
//        assert(scanf("%i %i %i", A + a, B + a, D + a) == 3);
//    }
//    Init(N, A, B, D);
//    for(int a = 0; a < Q; a++){
//        int S, T;
//        assert(scanf("%i %i", &S, &T) == 2);
//        int *X = (int*)malloc(sizeof(int) * S);
//        int *Y = (int*)malloc(sizeof(int) * T);
//        for(int b = 0; b < S; b++){
//            assert(scanf("%i", X + b) == 1);
//        }
//        for(int b = 0; b < T; b++){
//            assert(scanf("%i", Y + b) == 1);
//        }
//        printf("%i\n", Query(S, X, T, Y));
//        free(X);
//        free(Y);
//    }
//    free(A);
//    free(B);
//    free(D);
//}

Compilation message (stderr)

factories.cpp:3:194: note: #pragma message: Compiling at: Mon May  3 23:26:46 2021. Executing File: factories.cpp. If this date is not the same as the submission date, it could be an indication that the submission was rejudged.
    3 | #pragma message("Compiling at: " __TIMESTAMP__ ". Executing File: " __FILE__ ". If this date is not the same as the submission date, it could be an indication that the submission was rejudged.")
      |                                                                                                                                                                                                  ^

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