oj.uz

Submission #629009

# Submission time Handle Problem Language Result Execution time Memory
629009 2022-08-13T23:26:03 Z X_Ray Factories (JOI14_factories) C++14
100 / 100
 4804 ms 195408 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize ("O2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("strict-overflow")
//#pragma GCC target("avx,avx2,fma")
//#pragma comment(linker, "/STACK:268435456");
#define pb push_back
#define mp make_pair
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll inf = 1e16;
bool blocked[500001];
int n, children[500001], par[500001], cnt[500001], uniRoot;
ll ans = 1e16, dis[500001][19];
vector<pair<int, int>> adj[500001];
gp_hash_table<int, ll> minDis;
void DFS(int u, int prv){
    children[u] = 1;
    for(auto& i: adj[u]){
        if(blocked[i.first] || i.first == prv) continue;
        DFS(i.first, u);
        children[u] += children[i.first];
    }
}
int secDFS(int u, int prv){
    bool flag = 1;
    for(auto& i: adj[u]) if(! blocked[i.first] && children[i.first]*2 > children[u]) flag = 0;
    if(flag) return u;
    int anc = -1;
    for(auto& i: adj[u]){
        if(i.first == prv || blocked[i.first]) continue;
        children[u] -= children[i.first];
        children[i.first] += children[u];
        if(anc == -1) anc = secDFS(i.first, u);
        children[i.first] -= children[u];
        children[u] += children[i.first];
    }
    return anc;
}
void distDFS(int u, int prv, ll curDis, int root){
    dis[u][cnt[u]++] = curDis;
    for(auto& i: adj[u]){
        if(blocked[i.first] || i.first == prv) continue;
        distDFS(i.first, u, curDis+i.second, root);
    }
}
int decompose(int u){
    DFS(u, -1);
    int root = secDFS(u, -1);
    distDFS(root, -1, 0, root);
    blocked[root] = 1;
    for(auto& i: adj[root]) {
        if(blocked[i.first]) continue;
        int nextRoot = decompose(i.first);
        par[nextRoot] = root;
    }
    return root;
}
void Init(int N, int A[], int B[], int C[]) {
    n = N;
    for(int i = 0; i < N-1; i++){
        adj[A[i]].pb(mp(B[i], C[i]));
        adj[B[i]].pb(mp(A[i], C[i]));
    }
    uniRoot = decompose(0);
    par[uniRoot] = -1;
}
ll Query(int S, int X[], int T, int Y[]){
    //The answer is the lowest LCA for a pair {X_i, Y_j} in the Centroid Tree
    //O(STlogN) Naive
    //How do we process queries in O((S+T)) or O((S+T)logN)?
    //Idea: for all S, update the shortest distance for all nodes between the root of the centroid tree and X_i, and for Y_i, move up the centroid tree and update the answer for each node.
    //The height of the centroid tree is O(logN), so we get O((S+T)logN)
    //We can use Euler Tour Trick to get distances in O(1)
    //Alternatively just store the distances
    ans = inf;
    minDis.clear();
    for(int i = 0; i < S; i++){
        int cur = X[i], curcnt = cnt[X[i]]-1;
        while(cur != -1){
            if(minDis.find(cur) == minDis.end()) minDis[cur] = inf;
            minDis[cur] = min(minDis[cur], dis[X[i]][curcnt--]);
            cur = par[cur];
        }
    }
    for(int i = 0; i < T; i++){
        int cur = Y[i], curcnt = cnt[Y[i]]-1;
        while(cur != -1){
            if(minDis.find(cur) != minDis.end()) ans = min(ans, minDis[cur]+dis[Y[i]][curcnt]);
            curcnt--;
            cur = par[cur];
        }
    }
    assert(ans != 0);
    return ans;
}
/*
int main() {
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    int A[6] = {0, 1, 2, 2, 4, 1}, B[6] = {1, 2, 3, 4, 5, 6}, C[6] = {4, 4, 5, 6, 5, 3};
    Init(7, A, B, C);
    int X1[2] = {0, 6}, Y1[2] = {3, 4};
    cout << Query(2, X1, 2, Y1) << "\n";
    int X2[3] = {0, 1, 3}, Y2[2] = {4, 6};
    cout << Query(3, X2, 2, Y2) << "\n";
    int X3[1] = {2}, Y3[1] = {5};
    cout << Query(1, X3, 1, Y3) << "\n";
}
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12372 KB Output is correct
2 Correct 422 ms 21436 KB Output is correct
3 Correct 559 ms 21288 KB Output is correct
4 Correct 429 ms 21840 KB Output is correct
5 Correct 525 ms 21668 KB Output is correct
6 Correct 242 ms 21248 KB Output is correct
7 Correct 549 ms 21128 KB Output is correct
8 Correct 584 ms 21292 KB Output is correct
9 Correct 564 ms 21664 KB Output is correct
10 Correct 249 ms 21240 KB Output is correct
11 Correct 555 ms 21188 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 1948 ms 124312 KB Output is correct
3 Correct 3086 ms 125708 KB Output is correct
4 Correct 678 ms 124972 KB Output is correct
5 Correct 3990 ms 148308 KB Output is correct
6 Correct 3728 ms 127440 KB Output is correct
7 Correct 1476 ms 42932 KB Output is correct
8 Correct 458 ms 43712 KB Output is correct
9 Correct 1792 ms 47108 KB Output is correct
10 Correct 1531 ms 44376 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12372 KB Output is correct
2 Correct 422 ms 21436 KB Output is correct
3 Correct 559 ms 21288 KB Output is correct
4 Correct 429 ms 21840 KB Output is correct
5 Correct 525 ms 21668 KB Output is correct
6 Correct 242 ms 21248 KB Output is correct
7 Correct 549 ms 21128 KB Output is correct
8 Correct 584 ms 21292 KB Output is correct
9 Correct 564 ms 21664 KB Output is correct
10 Correct 249 ms 21240 KB Output is correct
11 Correct 555 ms 21188 KB Output is correct
12 Correct 9 ms 12244 KB Output is correct
13 Correct 1948 ms 124312 KB Output is correct
14 Correct 3086 ms 125708 KB Output is correct
15 Correct 678 ms 124972 KB Output is correct
16 Correct 3990 ms 148308 KB Output is correct
17 Correct 3728 ms 127440 KB Output is correct
18 Correct 1476 ms 42932 KB Output is correct
19 Correct 458 ms 43712 KB Output is correct
20 Correct 1792 ms 47108 KB Output is correct
21 Correct 1531 ms 44376 KB Output is correct
22 Correct 2210 ms 138040 KB Output is correct
23 Correct 2356 ms 151444 KB Output is correct
24 Correct 3426 ms 139400 KB Output is correct
25 Correct 3653 ms 168080 KB Output is correct
26 Correct 3569 ms 152788 KB Output is correct
27 Correct 4804 ms 195408 KB Output is correct
28 Correct 886 ms 159760 KB Output is correct
29 Correct 3547 ms 152096 KB Output is correct
30 Correct 3627 ms 151768 KB Output is correct
31 Correct 3751 ms 152320 KB Output is correct
32 Correct 1353 ms 73536 KB Output is correct
33 Correct 458 ms 63880 KB Output is correct
34 Correct 935 ms 55300 KB Output is correct
35 Correct 904 ms 55008 KB Output is correct
36 Correct 1153 ms 55488 KB Output is correct
37 Correct 1216 ms 55500 KB Output is correct