oj.uz

Submission #398202

# Submission time Handle Problem Language Result Execution time Memory
398202 2021-05-03T23:26:45 Z Encodeous Factories (JOI14_factories) C++11
100 / 100
 5010 ms 311596 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 98756 KB Output is correct
2 Correct 411 ms 107844 KB Output is correct
3 Correct 423 ms 107864 KB Output is correct
4 Correct 407 ms 107780 KB Output is correct
5 Correct 437 ms 108048 KB Output is correct
6 Correct 303 ms 107780 KB Output is correct
7 Correct 439 ms 107888 KB Output is correct
8 Correct 431 ms 107900 KB Output is correct
9 Correct 470 ms 108000 KB Output is correct
10 Correct 340 ms 107804 KB Output is correct
11 Correct 440 ms 107828 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 98508 KB Output is correct
2 Correct 2208 ms 283672 KB Output is correct
3 Correct 3070 ms 285236 KB Output is correct
4 Correct 869 ms 284744 KB Output is correct
5 Correct 3894 ms 311596 KB Output is correct
6 Correct 3197 ms 288496 KB Output is correct
7 Correct 1139 ms 141592 KB Output is correct
8 Correct 471 ms 142148 KB Output is correct
9 Correct 1276 ms 147392 KB Output is correct
10 Correct 1195 ms 142856 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 98756 KB Output is correct
2 Correct 411 ms 107844 KB Output is correct
3 Correct 423 ms 107864 KB Output is correct
4 Correct 407 ms 107780 KB Output is correct
5 Correct 437 ms 108048 KB Output is correct
6 Correct 303 ms 107780 KB Output is correct
7 Correct 439 ms 107888 KB Output is correct
8 Correct 431 ms 107900 KB Output is correct
9 Correct 470 ms 108000 KB Output is correct
10 Correct 340 ms 107804 KB Output is correct
11 Correct 440 ms 107828 KB Output is correct
12 Correct 52 ms 98508 KB Output is correct
13 Correct 2208 ms 283672 KB Output is correct
14 Correct 3070 ms 285236 KB Output is correct
15 Correct 869 ms 284744 KB Output is correct
16 Correct 3894 ms 311596 KB Output is correct
17 Correct 3197 ms 288496 KB Output is correct
18 Correct 1139 ms 141592 KB Output is correct
19 Correct 471 ms 142148 KB Output is correct
20 Correct 1276 ms 147392 KB Output is correct
21 Correct 1195 ms 142856 KB Output is correct
22 Correct 2901 ms 286148 KB Output is correct
23 Correct 2845 ms 288564 KB Output is correct
24 Correct 4188 ms 288368 KB Output is correct
25 Correct 4064 ms 292340 KB Output is correct
26 Correct 4003 ms 287808 KB Output is correct
27 Correct 5010 ms 306004 KB Output is correct
28 Correct 1069 ms 286968 KB Output is correct
29 Correct 4075 ms 287656 KB Output is correct
30 Correct 3977 ms 286660 KB Output is correct
31 Correct 3917 ms 287296 KB Output is correct
32 Correct 1264 ms 144828 KB Output is correct
33 Correct 463 ms 141328 KB Output is correct
34 Correct 877 ms 138440 KB Output is correct
35 Correct 865 ms 138528 KB Output is correct
36 Correct 1107 ms 139140 KB Output is correct
37 Correct 1098 ms 139216 KB Output is correct