Submission #398199

#	Time	Username	Problem	Language	Result	Execution time	Memory
398199		Encodeous	Factories (JOI14_factories)	C++11	15 / 100	1551 ms	190208 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 cur = 0;
int head[500001], vnext[1000001], adj[1000001], weight[1000001];
int cnt[500001];
int cqstat[500001];
bitset<500001> blocked;
int parent[500001];
ll ct_val[500001];
ll ct_dist[20][500001];
int depth[500001];

//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]] * 2 > sz){
                p = v;
                v = adj[i];
                any = true;
                break;
            }
        }
        if(!any) return v;
    }
}
int tlen = 0;
int req_tour[500001];
int req_size(int x, int p){
    if(blocked[x]) return 0;
    cnt[x] = 1;
//    req_tour[tlen++] = x;
    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 req_dist(int x, int p, int d){
    if(blocked[x]) return;
    for(int i = head[x]; i != -1; i = vnext[i]){
        if(adj[i] != p && !blocked[x]){
            ct_dist[d][adj[i]] = ct_dist[d][x] + weight[i];
            req_dist(adj[i], x, d);
        }
    }
}
void build_centroid_tree(int x, int p, int d){
    tlen = 0;
    req_size(x, x);
    x = ffind_centroid(x);
    depth[x] = d;
    req_dist(x, x, d);
    blocked[x] = true;
    parent[x] = p;
    for(int i = head[x]; i != -1; i = vnext[i]){
        if(!blocked[adj[i]]){
            build_centroid_tree(adj[i], x, d+1);
        }
    }
}
#define get_dist(c,i) (ct_dist[depth[c]][i])
void update(int x, int qstat){
    int idx = 0;
    for(int c = x; c != -1; c = parent[c]){
        ll d = get_dist(c,x);
        if(cqstat[c] != qstat) {
            ct_val[c] = d;
            cqstat[c] = qstat;
        }
        ct_val[c] = min(ct_val[c], d);
        idx++;
    }
}
ll query(int x, int qstat){
    int q = 0;
    ll minv = 1e17;
    for(int c = x ; c != -1; c = parent[c]) {
        ll d = get_dist(c,x);
        if(cqstat[c] == qstat){
            minv = min(minv, ct_val[c] + d);
        }
        q++;
    }
    return minv;
}
void update2(int x){
    for(int c = x; c != -1; c = parent[c]){
        ll d = get_dist(c,x);
        ct_val[c] = min(ct_val[c], d);
    }
}
void clean(int x){
    for(int c = x; c != -1; c = parent[c]){
        ct_val[c] = 1e17;
    }
}
ll query2(int x){
    ll minv = 1e17;
    for(int c = x ; c != -1; c = parent[c]) {
        ll d = get_dist(c,x);
        minv = min(minv, ct_val[c] + d);
    }
    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);
    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];
    }
    auto start = chrono::system_clock::now();
    build_centroid_tree(x, -1, 0);
    auto dur = chrono::duration<double, std::milli>(chrono::system_clock::now() - start).count();
    assert(dur <= 1000);
}
int curqstat = 1;
ll Query(int S, int X[], int T, int Y[]){
    if(false){
        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;
    }
    for(int i = 0; i < S; i++){
        update2(X[i]);
    }
    ll mind = 1e17;
    for(int i = 0; i < T; i++){
        mind = min(mind, query2(Y[i]));
    }
    for(int i = 0; i < S; i++){
        clean(X[i]);
    }
    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:25:07 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: 0 / 18
• Subtask 3: 0 / 67