oj.uz

Submission #1103220

# Submission time Handle Problem Language Result Execution time Memory
1103220 2024-10-20T14:29:45 Z InvMOD Factories (JOI14_factories) C++14
100 / 100
 3027 ms 164948 KB 
#include<bits/stdc++.h>
#include<factories.h>

#define fi first
#define se second
 
using namespace std;
 
using ll = long long;
 
template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}
 
const int N = 5e5+5;
const int lg = 21;
const ll inf = 1e15;
 
int n, sz[N];
int par_Cen[N], level[N];
ll dist[lg][N], mn_Dist[N];
bool del[N];
vector<pair<int,int>> adj[N];
 
 
int get_Size(int x, int p){
    sz[x] = 1;
    for(pair<int,int> e : adj[x])if(e.fi != p && !del[e.fi]){
        sz[x] += get_Size(e.fi, x);
    }
    return sz[x];
}
 
int Centroid(int x, int p, int trsz){
    for(pair<int,int> e : adj[x])if(e.fi != p && !del[e.fi] && (sz[e.fi]<<1) > trsz){
        return Centroid(e.fi, x, trsz);
    }
    return x;
}
 
void build_dist(int x, int p, int cur_lev){
    for(pair<int,int> e : adj[x])if(e.fi != p && !del[e.fi]){
        dist[cur_lev][e.fi] = dist[cur_lev][x] + (1ll * e.se);
        build_dist(e.fi, x, cur_lev);
    }
    return;
}
 
void decompose(int x, int pre_cen){
    x = Centroid(x, -1, get_Size(x, -1));
    del[x] = true;
 
    level[x] = level[pre_cen] + 1;
    par_Cen[x] = pre_cen;
 
    dist[level[x]][x] = 0;
    build_dist(x, -1, level[x]);
 
    for(pair<int,int> e : adj[x]){
        if(!del[e.fi]){
            decompose(e.fi, x);
        }
    }
    return;
}
 
ll get_Dist(int a, int b){
    int u = a, v = b;
    if(level[u] > level[v]) swap(u, v);
    while(level[v] > level[u]) v = par_Cen[v];
 
    while(u != v){
        u = par_Cen[u], v = par_Cen[v];
    }
    return dist[level[v]][a] + dist[level[v]][b];
}
 
void add_Cen(int a){
    int u = a;
    while(level[u]){
        ckmn(mn_Dist[u], get_Dist(a, u));
        u = par_Cen[u];
    }
    return;
}
 
void rem_Cen(int u){
    while(level[u]){
        mn_Dist[u] = inf;
        u = par_Cen[u];
    }
    return;
}
 
ll Query_Cen(int a){
    int u = a; ll answer = inf;
    while(level[u]){
        ckmn(answer, get_Dist(a, u) + mn_Dist[u]);
        u = par_Cen[u];
    }
    return answer;
}
 
ll Query(int S, int X[], int T, int Y[]){
    for(int i = 0; i < S; i++){
        add_Cen(X[i]+1);
    }
 
    ll answer = inf;
    for(int i = 0; i < T; i++){
        ckmn(answer, Query_Cen(Y[i]+1));
    }
 
    for(int i = 0; i < S; i++){
        rem_Cen(X[i]+1);
    }
    return answer;
}
 
void Init(int _N, int A[], int B[], int D[]){
    n = _N;
 
    for(int i = 0; i < n-1; i++){
        int u = A[i]+1, v = B[i]+1, w = D[i];
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }
 
    decompose(1, 0);
    for(int i = 1; i <= n; i++){
        mn_Dist[i] = inf;
    }
    return;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 53840 KB Output is correct
2 Correct 257 ms 62280 KB Output is correct
3 Correct 304 ms 66464 KB Output is correct
4 Correct 302 ms 66380 KB Output is correct
5 Correct 341 ms 66632 KB Output is correct
6 Correct 136 ms 43848 KB Output is correct
7 Correct 555 ms 64320 KB Output is correct
8 Correct 306 ms 66376 KB Output is correct
9 Correct 350 ms 66716 KB Output is correct
10 Correct 150 ms 43936 KB Output is correct
11 Correct 333 ms 64444 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 51792 KB Output is correct
2 Correct 1111 ms 130592 KB Output is correct
3 Correct 1639 ms 143504 KB Output is correct
4 Correct 370 ms 75952 KB Output is correct
5 Correct 2492 ms 164948 KB Output is correct
6 Correct 1897 ms 143688 KB Output is correct
7 Correct 693 ms 91796 KB Output is correct
8 Correct 206 ms 52924 KB Output is correct
9 Correct 873 ms 95188 KB Output is correct
10 Correct 773 ms 92232 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 53840 KB Output is correct
2 Correct 257 ms 62280 KB Output is correct
3 Correct 304 ms 66464 KB Output is correct
4 Correct 302 ms 66380 KB Output is correct
5 Correct 341 ms 66632 KB Output is correct
6 Correct 136 ms 43848 KB Output is correct
7 Correct 555 ms 64320 KB Output is correct
8 Correct 306 ms 66376 KB Output is correct
9 Correct 350 ms 66716 KB Output is correct
10 Correct 150 ms 43936 KB Output is correct
11 Correct 333 ms 64444 KB Output is correct
12 Correct 8 ms 51792 KB Output is correct
13 Correct 1111 ms 130592 KB Output is correct
14 Correct 1639 ms 143504 KB Output is correct
15 Correct 370 ms 75952 KB Output is correct
16 Correct 2492 ms 164948 KB Output is correct
17 Correct 1897 ms 143688 KB Output is correct
18 Correct 693 ms 91796 KB Output is correct
19 Correct 206 ms 52924 KB Output is correct
20 Correct 873 ms 95188 KB Output is correct
21 Correct 773 ms 92232 KB Output is correct
22 Correct 1508 ms 129584 KB Output is correct
23 Correct 1539 ms 132644 KB Output is correct
24 Correct 2277 ms 141856 KB Output is correct
25 Correct 2096 ms 143856 KB Output is correct
26 Correct 2044 ms 142428 KB Output is correct
27 Correct 3027 ms 159164 KB Output is correct
28 Correct 422 ms 75952 KB Output is correct
29 Correct 2253 ms 142060 KB Output is correct
30 Correct 2068 ms 141640 KB Output is correct
31 Correct 2039 ms 142152 KB Output is correct
32 Correct 922 ms 95304 KB Output is correct
33 Correct 223 ms 52924 KB Output is correct
34 Correct 543 ms 86600 KB Output is correct
35 Correct 533 ms 86600 KB Output is correct
36 Correct 762 ms 91292 KB Output is correct
37 Correct 817 ms 91208 KB Output is correct