oj.uz

Submission #1028854

# Submission time Handle Problem Language Result Execution time Memory
1028854 2024-07-20T09:30:35 Z KienTran Factories (JOI14_factories) C++14
100 / 100
 2753 ms 317548 KB 
#include <bits/stdc++.h>
#include "factories.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
 
const int O = 2e6 + 5;
const int mod = 1e9 + 7; //998244353;
const long long inf = 1e16;
int pr[] = {167772161, 469762049, 754974721, 1045430273, 1051721729, 1053818881};
 
int n, q, Time, p[O], h[O], rp[O], in[O], child[O], f[22][O];
long long d[O], val[20][O];
vector <pair <int, int>> g[O];
pair <long long, int> dp[2][O];
bool del[O];
 
void init(int u, int par = -1){
    in[u] = ++ Time; rp[Time] = u;
    for (auto &to : g[u]){
        int v = to.first;
        int w = to.second;
        if (v != par){
            h[v] = h[u] + 1;
            d[v] = d[u] + w;
            init(v, u);
            rp[++ Time] = u;
        }
    }
}
 
int Lca(int u, int v){
    int l = min(in[u], in[v]);
    int r = max(in[u], in[v]);
    if (l == r) return u;
 
    int len = log2(r - l + 1);
    return h[f[len][l]] < h[f[len][r - (1 << len) + 1]] ? f[len][l] : f[len][r - (1 << len) + 1];
}
 
long long dist(int u, int v){
    return d[u] + d[v] - 2 * d[Lca(u, v)];
}
 
void dfs_init(int u, int par = -1){
    child[u] = 1;
    for (auto &to : g[u]){
        int v = to.first;
        int w = to.second;
        if (v != par && !del[v]){
            dfs_init(v, u);
            child[u] += child[v];
        }
    }
}
 
int centroid(int u, int par, int Nchild){
    for (auto &to : g[u]){
        int v = to.first;
        if (v != par && !del[v] && child[v] * 2 > Nchild) return centroid(v, u, Nchild);
    }
    return u;
}
 
int dfs_centroid(int u){
    dfs_init(u);
    int root = centroid(u, -1, child[u]);
 
    del[root] = 1;
    for (auto &v : g[root]){
        if (!del[v.first]){
            int nxt = dfs_centroid(v.first);
            p[nxt] = root;
 
            //cout << root << " " << nxt << " " << x << endl;
        }
    }
 
    return root;
}
 
void Init(int N, int A[], int B[], int D[]){
    n = N;
    for (int i = 0; i < n - 1; ++ i){
        int u, v, w;
        u = A[i]; v = B[i]; w = D[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
 
    memset(p, -1, sizeof(p));
 
    init(0);
 
    for (int i = 1; i <= Time; ++ i){
        f[0][i] = rp[i];
    }
 
    for (int i = 1; i <= 21; ++ i){
        for (int j = 1; j - 1 + (1 << i) <= Time; ++ j){
            f[i][j] = h[f[i - 1][j]] < h[f[i - 1][j + (1 << (i - 1))]] ? f[i - 1][j] : f[i - 1][j + (1 << (i - 1))];
        }
    }
 
    //cout << "deba" << endl;
    dfs_centroid(0);
    //cout << "deba" << endl;
 
    for (int i = 0; i < n; ++ i){
        int u = i, cnt = 0;
        while (u != -1){
            val[cnt ++][i] = dist(i, u);
            u = p[u];
        }
    }
 
    for (int i = 0; i < n; ++ i) dp[0][i] = dp[1][i] = {inf, -1};
    return;
}
 
long long Query(int S, int X[], int T, int Y[]){
    long long res = inf;
    for (int i = 0; i < S; ++ i){
        int u = X[i], cnt = 0;
        pair <long long, int> cur = {0, -1};
        while (u != -1){
            cur.first = val[cnt ++][X[i]];
            if (dp[0][u].first > cur.first){
                pair <long long, int> x = dp[0][u];
                dp[0][u] = cur;
                if (cur.second != x.second) dp[1][u] = x;
            }
            else{
                if (dp[1][u].first > cur.first && cur.second != dp[0][u].second){
                    dp[1][u] = cur;
                }
                //break;
            }
            cur.second = u;
            u = p[u];
        }
    }
 
    /*for (int i = 0; i < n; ++ i){
        cout << i << " : " << dp[0][i].first << " " << dp[0][i].second << endl;
        cout << i << " : " << dp[1][i].first << " " << dp[1][i].second << endl;
    }*/
 
    for (int i = 0; i < T; ++ i){
        int u = Y[i], cnt = 0;
 
        res = min(res, dp[0][u].first);
        while (u != -1){
            int par = p[u];
            if (par != -1){
                long long cur = val[++ cnt][Y[i]];
                res = min(res, cur + (dp[0][par].second == u ? dp[1][par].first : dp[0][par].first));
            }
            u = par;
        }
    }
 
    for (int i = 0; i < S; ++ i){
        int u = X[i];
        while (u != -1){
            dp[0][u] = dp[1][u] = {inf, -1};
            u = p[u];
        }
    }
 
    return res;
}
 
/*main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    int A[1000], B[1000], D[1000];
    for (int i = 0; i < n - 1; ++ i){
        cin >> A[i] >> B[i] >> D[i];
    }
 
    Init(n, A, B, D);
 
    //cout << Time << " " << Lca(2, 4) << endl;
 
    for (int i = 1; i <= q; ++ i){
        int S, T;
        cin >> S >> T;
        int X[1000], Y[1000];
        for (int j = 0; j < S; ++ j){
            int x; cin >> x;
            X[j] = x;
        }
 
        for (int j = 0; j < T; ++ j){
            int x; cin >> x;
            Y[j] = x;
        }
 
        cout << "debug " << i << endl;
        cout << Query(S, X, T, Y) << "\n";
        cout << "debug " << i << endl << endl;
    }
 
}*/
 
/***
7 1
0 1 1
1 2 2
2 3 3
3 4 4
4 5 5
5 6 6
2 2
0 2
5 4
***/

Compilation message

factories.cpp: In function 'void dfs_init(int, int)':
factories.cpp:50:13: warning: unused variable 'w' [-Wunused-variable]
   50 |         int w = to.second;
      |             ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 55644 KB Output is correct
2 Correct 240 ms 74064 KB Output is correct
3 Correct 268 ms 74352 KB Output is correct
4 Correct 248 ms 74320 KB Output is correct
5 Correct 283 ms 74576 KB Output is correct
6 Correct 141 ms 73808 KB Output is correct
7 Correct 241 ms 74320 KB Output is correct
8 Correct 254 ms 74320 KB Output is correct
9 Correct 312 ms 74704 KB Output is correct
10 Correct 135 ms 73808 KB Output is correct
11 Correct 270 ms 74364 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 55432 KB Output is correct
2 Correct 1193 ms 267924 KB Output is correct
3 Correct 1686 ms 283852 KB Output is correct
4 Correct 387 ms 215748 KB Output is correct
5 Correct 2410 ms 312912 KB Output is correct
6 Correct 1735 ms 285776 KB Output is correct
7 Correct 613 ms 115020 KB Output is correct
8 Correct 262 ms 103876 KB Output is correct
9 Correct 773 ms 119376 KB Output is correct
10 Correct 712 ms 116340 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 55644 KB Output is correct
2 Correct 240 ms 74064 KB Output is correct
3 Correct 268 ms 74352 KB Output is correct
4 Correct 248 ms 74320 KB Output is correct
5 Correct 283 ms 74576 KB Output is correct
6 Correct 141 ms 73808 KB Output is correct
7 Correct 241 ms 74320 KB Output is correct
8 Correct 254 ms 74320 KB Output is correct
9 Correct 312 ms 74704 KB Output is correct
10 Correct 135 ms 73808 KB Output is correct
11 Correct 270 ms 74364 KB Output is correct
12 Correct 23 ms 55432 KB Output is correct
13 Correct 1193 ms 267924 KB Output is correct
14 Correct 1686 ms 283852 KB Output is correct
15 Correct 387 ms 215748 KB Output is correct
16 Correct 2410 ms 312912 KB Output is correct
17 Correct 1735 ms 285776 KB Output is correct
18 Correct 613 ms 115020 KB Output is correct
19 Correct 262 ms 103876 KB Output is correct
20 Correct 773 ms 119376 KB Output is correct
21 Correct 712 ms 116340 KB Output is correct
22 Correct 1619 ms 274772 KB Output is correct
23 Correct 1622 ms 279508 KB Output is correct
24 Correct 2105 ms 293716 KB Output is correct
25 Correct 2295 ms 297736 KB Output is correct
26 Correct 2360 ms 294068 KB Output is correct
27 Correct 2753 ms 317548 KB Output is correct
28 Correct 463 ms 228068 KB Output is correct
29 Correct 2041 ms 293644 KB Output is correct
30 Correct 2245 ms 292952 KB Output is correct
31 Correct 2164 ms 293716 KB Output is correct
32 Correct 801 ms 121920 KB Output is correct
33 Correct 229 ms 105652 KB Output is correct
34 Correct 454 ms 111444 KB Output is correct
35 Correct 477 ms 111344 KB Output is correct
36 Correct 685 ms 114516 KB Output is correct
37 Correct 698 ms 114728 KB Output is correct