oj.uz

Submission #772160

# Submission time Handle Problem Language Result Execution time Memory
772160 2023-07-03T17:15:59 Z Essa2006 Factories (JOI14_factories) C++14
100 / 100
 5747 ms 139116 KB 
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
#define MAX_N 500000
const ll inf=1e15, lg=19;
int n;
ll Dis[MAX_N];
int dpth[MAX_N];
vector<vector<int>>BB(MAX_N), AA(MAX_N);
int up[MAX_N][lg+1];
 
void pre(){
    for(int i=0;i<MAX_N;i++){
        Dis[i]=inf, dpth[i]=2*n;
    }
}
 
void bfs(int ind){
    queue<int>q;
    q.push(ind);
    up[ind][0]=ind;
    Dis[ind]=dpth[ind]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int j=1;j<=lg;j++){
             up[u][j]=up[up[u][j-1]][j-1];
             if(up[u][j]==0)
                break;
        }
        for(int i=0;i<AA[u].size();i++){
            int v=AA[u][i];
            if(dpth[u]+1<dpth[v]){
                dpth[v]=dpth[u]+1, Dis[v]=Dis[u]+BB[u][i];
                up[v][0]=u;
                q.push(v);
            }
        }
    }
}
int lca(int u, int v){
    // u
 
    // v
    if(dpth[u]>dpth[v])
        swap(u, v);
    for(int j=lg;j>=0;j--){
        if(dpth[up[v][j]]>=dpth[u])
            v=up[v][j];
    }
    if(u==v)
        return u;
    for(int j=lg;j>=0;j--){
        if(up[u][j]!=up[v][j])
            u=up[u][j], v=up[v][j];
    }
    return up[v][0];
}
inline ll get_dis(int u, int v){
    return Dis[u]+Dis[v]-2*Dis[lca(u, v)];
}
void Init(int N, int A[], int B[], int D[]) {
    n=N;
    pre();
    for(int i=0;i<n-1;i++){
        int u=A[i], v=B[i], w=D[i];
        AA[u].push_back(v);
        AA[v].push_back(u);
        BB[u].push_back(w);
        BB[v].push_back(w);
    }
    bfs(0);
}
 
long long Query(int S, int X[], int T, int Y[]) {
    if(S>45 && T>45){
        vector<ll>D(n, inf);
        vector<bool>In_y(n, 0), Vis(n, 0);
        for(int i=0;i<T;i++){
            In_y[Y[i]]=1;
        }
        priority_queue<array<ll, 2>>q;
        for(int i=0;i<S;i++){
            q.push({0, X[i]});
            D[X[i]]=0;
        }
        while(!q.empty()){
            int u=q.top()[1];
            q.pop();
            if(Vis[u])
                continue;
            Vis[u]=1;
            if(In_y[u])
                return D[u];
            for(int i=0;i<AA[u].size();i++){
                int v=AA[u][i], w=BB[u][i];
                if(D[u]+w<D[v]){
                    D[v]=D[u]+w;
                    q.push({-D[v], v});
                }
            }
        }
    }
    ll ans=inf;
    for(int i=0;i<S;i++){
        for(int j=0;j<T;j++){
            ans=min(ans, get_dis(X[i], Y[j]));
        }
    }
    return ans;
}

Compilation message

factories.cpp: In function 'void bfs(int)':
factories.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int i=0;i<AA[u].size();i++){
      |                     ~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:101:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |             for(int i=0;i<AA[u].size();i++){
      |                         ~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 30036 KB Output is correct
2 Correct 524 ms 38496 KB Output is correct
3 Correct 333 ms 38448 KB Output is correct
4 Correct 994 ms 38608 KB Output is correct
5 Correct 468 ms 38472 KB Output is correct
6 Correct 636 ms 38692 KB Output is correct
7 Correct 325 ms 38604 KB Output is correct
8 Correct 763 ms 38488 KB Output is correct
9 Correct 451 ms 38472 KB Output is correct
10 Correct 612 ms 38732 KB Output is correct
11 Correct 325 ms 38476 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 29820 KB Output is correct
2 Correct 1642 ms 114236 KB Output is correct
3 Correct 3820 ms 111444 KB Output is correct
4 Correct 1112 ms 117056 KB Output is correct
5 Correct 3988 ms 113192 KB Output is correct
6 Correct 2837 ms 113292 KB Output is correct
7 Correct 5747 ms 54068 KB Output is correct
8 Correct 1771 ms 56344 KB Output is correct
9 Correct 3818 ms 55584 KB Output is correct
10 Correct 3327 ms 55528 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 30036 KB Output is correct
2 Correct 524 ms 38496 KB Output is correct
3 Correct 333 ms 38448 KB Output is correct
4 Correct 994 ms 38608 KB Output is correct
5 Correct 468 ms 38472 KB Output is correct
6 Correct 636 ms 38692 KB Output is correct
7 Correct 325 ms 38604 KB Output is correct
8 Correct 763 ms 38488 KB Output is correct
9 Correct 451 ms 38472 KB Output is correct
10 Correct 612 ms 38732 KB Output is correct
11 Correct 325 ms 38476 KB Output is correct
12 Correct 21 ms 29820 KB Output is correct
13 Correct 1642 ms 114236 KB Output is correct
14 Correct 3820 ms 111444 KB Output is correct
15 Correct 1112 ms 117056 KB Output is correct
16 Correct 3988 ms 113192 KB Output is correct
17 Correct 2837 ms 113292 KB Output is correct
18 Correct 5747 ms 54068 KB Output is correct
19 Correct 1771 ms 56344 KB Output is correct
20 Correct 3818 ms 55584 KB Output is correct
21 Correct 3327 ms 55528 KB Output is correct
22 Correct 1373 ms 122692 KB Output is correct
23 Correct 2023 ms 126432 KB Output is correct
24 Correct 1367 ms 121944 KB Output is correct
25 Correct 1585 ms 122864 KB Output is correct
26 Correct 1636 ms 118332 KB Output is correct
27 Correct 2260 ms 122356 KB Output is correct
28 Correct 1522 ms 139116 KB Output is correct
29 Correct 3360 ms 118400 KB Output is correct
30 Correct 4099 ms 118244 KB Output is correct
31 Correct 4710 ms 118392 KB Output is correct
32 Correct 718 ms 56988 KB Output is correct
33 Correct 729 ms 59120 KB Output is correct
34 Correct 464 ms 53908 KB Output is correct
35 Correct 509 ms 54032 KB Output is correct
36 Correct 538 ms 53760 KB Output is correct
37 Correct 548 ms 53736 KB Output is correct