oj.uz

Submission #772146

# Submission time Handle Problem Language Result Execution time Memory
772146 2023-07-03T17:06:58 Z Essa2006 Factories (JOI14_factories) C++14
100 / 100
 5526 ms 139016 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
// #define MAX_Q          100000
// #define MAX_SUM_ST    1000000
// #define MAX_VALUE  1000000000
// static int N, Q;
// static int A[MAX_N], B[MAX_N], D[MAX_N];
// static int S[MAX_N];
// static int T[MAX_N];
// static int X[MAX_SUM_ST];
// static int Y[MAX_SUM_ST];
// static int Qx[MAX_N];
// static int Qy[MAX_N];
 
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;
}
// int main() {
// 
//   int i, j, k;
//   int STop, TTop;
// 
//   if (2 != scanf("%d%d", &N, &Q)) {
//     fprintf(stderr, "error: cannot read N and Q.\n");
//     exit(1);
//   }
//   if (!(2 <= N && N <= MAX_N)) {
//     fprintf(stderr, "error: N is out of bounds.\n");
//     exit(1);
//   }
//   if (!(1 <= Q && Q <= MAX_Q)) {
//     fprintf(stderr, "error: Q is out of bounds.\n");
//     exit(1);
//   }
//   for (i = 0; i < N - 1; ++i) {
//     if (1 != scanf("%d", &A[i])) {
//       fprintf(stderr, "error: cannot read A[%d].\n", i);
//       exit(1);
//     }
//     if (!(0 <= A[i] && A[i] <= N - 1)) {
//       fprintf(stderr, "error: A[%d] is out of bounds.\n", i);
//       exit(1);
//     }
//     if (1 != scanf("%d", &B[i])) {
//       fprintf(stderr, "error: cannot read B[%d].\n", i);
//       exit(1);
//     }
//     if (!(0 <= B[i] && B[i] <= N - 1)) {
//       fprintf(stderr, "error: B[%d] is out of bounds.\n", i);
//       exit(1);
//     }
//     if (A[i] == B[i]) {
//       fprintf(stderr, "error: B[%d] is equal to A[%d].\n", i, i);
//       exit(1);
//     }
//     if (1 != scanf("%d", &D[i])) {
//       fprintf(stderr, "error: cannot read D[%d].\n", i);
//       exit(1);
//     }
//     if (!(1 <= D[i] && D[i] <= MAX_VALUE)) {
//       fprintf(stderr, "error: D[%d] is out of bounds.\n", i);
//       exit(1);
//     }
//   }
// 
//   STop = 0;
//   TTop = 0;
// 
//   for (j = 0; j < Q; ++j) {
//     if (2 != scanf("%d%d", &S[j], &T[j])) {
//       fprintf(stderr, "error: cannot read L[%d] and R[%d].\n", j, j);
//       exit(1);
//     }
// 
//     if(STop + S[j] > MAX_SUM_ST) {
//       fprintf(stderr, "error: S[0] + S[1] + ... + S[%d] is out of bounds.\n", j);
//       exit(1);
//     }
// 
//     if(TTop + T[j] > MAX_SUM_ST) {
//       fprintf(stderr, "error: T[0] + T[1] + ... + T[%d] is out of bounds.\n", j);
//       exit(1);
//     }
// 
//     for (k = 0; k < S[j]; ++k, ++STop) {
//       if (1 != scanf("%d", &X[STop])) {
//         fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k);
//         exit(1);
//       }
// 
//       if (!(0 <= X[STop] && X[STop] <= N - 1)) {
//         fprintf(stderr, "error: cannot read X[%d][%d].\n", j, k);
//         exit(1);
//       }
//     }
// 
//     for (k = 0; k < T[j]; ++k, ++TTop) {
//       if (1 != scanf("%d", &Y[TTop])) {
//         fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k);
//         exit(1);
//       }
// 
//       if (!(0 <= Y[TTop] && Y[TTop] <= N - 1)) {
//         fprintf(stderr, "error: cannot read Y[%d][%d].\n", j, k);
//         exit(1);
//       }
//     }
//   }
// 
//   STop = 0;
//   TTop = 0;
//   Init(N, A, B, D);
// 
//   for (j = 0; j < Q; ++j) {
//     for (k = 0; k < S[j]; k++) {
//         Qx[k] = X[STop++];
//     }
//     for (k = 0; k < T[j]; k++) {
//         Qy[k] = Y[TTop++];
//     }
// 
//     printf("%lld\n", Query(S[j], Qx, T[j], Qy));
//   }
// 
// 
//   return 0;
// }

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 30032 KB Output is correct
2 Correct 518 ms 38492 KB Output is correct
3 Correct 333 ms 38448 KB Output is correct
4 Correct 968 ms 38696 KB Output is correct
5 Correct 431 ms 38544 KB Output is correct
6 Correct 611 ms 38664 KB Output is correct
7 Correct 343 ms 38424 KB Output is correct
8 Correct 734 ms 38480 KB Output is correct
9 Correct 454 ms 38460 KB Output is correct
10 Correct 594 ms 38668 KB Output is correct
11 Correct 346 ms 38428 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 29860 KB Output is correct
2 Correct 1643 ms 114208 KB Output is correct
3 Correct 3853 ms 111472 KB Output is correct
4 Correct 1077 ms 116968 KB Output is correct
5 Correct 3799 ms 113180 KB Output is correct
6 Correct 2609 ms 113264 KB Output is correct
7 Correct 5526 ms 54136 KB Output is correct
8 Correct 1738 ms 56444 KB Output is correct
9 Correct 4964 ms 55528 KB Output is correct
10 Correct 3170 ms 55436 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 30032 KB Output is correct
2 Correct 518 ms 38492 KB Output is correct
3 Correct 333 ms 38448 KB Output is correct
4 Correct 968 ms 38696 KB Output is correct
5 Correct 431 ms 38544 KB Output is correct
6 Correct 611 ms 38664 KB Output is correct
7 Correct 343 ms 38424 KB Output is correct
8 Correct 734 ms 38480 KB Output is correct
9 Correct 454 ms 38460 KB Output is correct
10 Correct 594 ms 38668 KB Output is correct
11 Correct 346 ms 38428 KB Output is correct
12 Correct 16 ms 29860 KB Output is correct
13 Correct 1643 ms 114208 KB Output is correct
14 Correct 3853 ms 111472 KB Output is correct
15 Correct 1077 ms 116968 KB Output is correct
16 Correct 3799 ms 113180 KB Output is correct
17 Correct 2609 ms 113264 KB Output is correct
18 Correct 5526 ms 54136 KB Output is correct
19 Correct 1738 ms 56444 KB Output is correct
20 Correct 4964 ms 55528 KB Output is correct
21 Correct 3170 ms 55436 KB Output is correct
22 Correct 1291 ms 122696 KB Output is correct
23 Correct 2095 ms 126492 KB Output is correct
24 Correct 1460 ms 121860 KB Output is correct
25 Correct 1627 ms 122956 KB Output is correct
26 Correct 1644 ms 118364 KB Output is correct
27 Correct 2169 ms 122356 KB Output is correct
28 Correct 1615 ms 139016 KB Output is correct
29 Correct 3509 ms 118256 KB Output is correct
30 Correct 4311 ms 118224 KB Output is correct
31 Correct 5212 ms 118276 KB Output is correct
32 Correct 927 ms 56912 KB Output is correct
33 Correct 887 ms 59196 KB Output is correct
34 Correct 600 ms 53988 KB Output is correct
35 Correct 589 ms 54000 KB Output is correct
36 Correct 728 ms 53756 KB Output is correct
37 Correct 664 ms 53748 KB Output is correct