oj.uz

Submission #772121

# Submission time Handle Problem Language Result Execution time Memory
772121 2023-07-03T16:30:23 Z Essa2006 Factories (JOI14_factories) C++14
100 / 100
 7645 ms 183276 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;
vector<ll>Dis;
vector<int>dpth;
vector<vector<int>>BB, AA, up;
 
void pre(){
    Dis.clear(), dpth.clear(), AA.clear(), up.clear(), BB.clear();
    Dis.resize(n, inf), dpth.resize(n, 2*n), AA.resize(n), BB.resize(n), up.resize(n, vector<int>(lg+1));
}
 
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>20 && T>20){
        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:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int i=0;i<AA[u].size();i++){
      |                     ~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:111:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             for(int i=0;i<AA[u].size();i++){
      |                         ~^~~~~~~~~~~~~
factories.cpp: At global scope:
factories.cpp:21:12: warning: 'Qy' defined but not used [-Wunused-variable]
   21 | static int Qy[MAX_N];
      |            ^~
factories.cpp:20:12: warning: 'Qx' defined but not used [-Wunused-variable]
   20 | static int Qx[MAX_N];
      |            ^~
factories.cpp:19:12: warning: 'Y' defined but not used [-Wunused-variable]
   19 | static int Y[MAX_SUM_ST];
      |            ^
factories.cpp:18:12: warning: 'X' defined but not used [-Wunused-variable]
   18 | static int X[MAX_SUM_ST];
      |            ^
factories.cpp:17:12: warning: 'T' defined but not used [-Wunused-variable]
   17 | static int T[MAX_N];
      |            ^
factories.cpp:16:12: warning: 'S' defined but not used [-Wunused-variable]
   16 | static int S[MAX_N];
      |            ^
factories.cpp:15:32: warning: 'D' defined but not used [-Wunused-variable]
   15 | static int A[MAX_N], B[MAX_N], D[MAX_N];
      |                                ^
factories.cpp:15:22: warning: 'B' defined but not used [-Wunused-variable]
   15 | static int A[MAX_N], B[MAX_N], D[MAX_N];
      |                      ^
factories.cpp:15:12: warning: 'A' defined but not used [-Wunused-variable]
   15 | static int A[MAX_N], B[MAX_N], D[MAX_N];
      |            ^
factories.cpp:14:15: warning: 'Q' defined but not used [-Wunused-variable]
   14 | static int N, Q;
      |               ^
factories.cpp:14:12: warning: 'N' defined but not used [-Wunused-variable]
   14 | static int N, Q;
      |            ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 724 KB Output is correct
2 Correct 360 ms 9608 KB Output is correct
3 Correct 308 ms 9564 KB Output is correct
4 Correct 679 ms 9800 KB Output is correct
5 Correct 322 ms 9548 KB Output is correct
6 Correct 442 ms 9836 KB Output is correct
7 Correct 298 ms 9508 KB Output is correct
8 Correct 584 ms 9680 KB Output is correct
9 Correct 317 ms 9584 KB Output is correct
10 Correct 434 ms 9784 KB Output is correct
11 Correct 299 ms 9552 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 2072 ms 133840 KB Output is correct
3 Correct 5377 ms 131036 KB Output is correct
4 Correct 1334 ms 136544 KB Output is correct
5 Correct 6047 ms 132668 KB Output is correct
6 Correct 3843 ms 132832 KB Output is correct
7 Correct 7645 ms 34600 KB Output is correct
8 Correct 1947 ms 36944 KB Output is correct
9 Correct 5866 ms 35912 KB Output is correct
10 Correct 4315 ms 35924 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 724 KB Output is correct
2 Correct 360 ms 9608 KB Output is correct
3 Correct 308 ms 9564 KB Output is correct
4 Correct 679 ms 9800 KB Output is correct
5 Correct 322 ms 9548 KB Output is correct
6 Correct 442 ms 9836 KB Output is correct
7 Correct 298 ms 9508 KB Output is correct
8 Correct 584 ms 9680 KB Output is correct
9 Correct 317 ms 9584 KB Output is correct
10 Correct 434 ms 9784 KB Output is correct
11 Correct 299 ms 9552 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 2072 ms 133840 KB Output is correct
14 Correct 5377 ms 131036 KB Output is correct
15 Correct 1334 ms 136544 KB Output is correct
16 Correct 6047 ms 132668 KB Output is correct
17 Correct 3843 ms 132832 KB Output is correct
18 Correct 7645 ms 34600 KB Output is correct
19 Correct 1947 ms 36944 KB Output is correct
20 Correct 5866 ms 35912 KB Output is correct
21 Correct 4315 ms 35924 KB Output is correct
22 Correct 1334 ms 166728 KB Output is correct
23 Correct 2265 ms 170580 KB Output is correct
24 Correct 1406 ms 165924 KB Output is correct
25 Correct 1855 ms 167084 KB Output is correct
26 Correct 1626 ms 161956 KB Output is correct
27 Correct 2759 ms 166584 KB Output is correct
28 Correct 1623 ms 183276 KB Output is correct
29 Correct 3399 ms 162060 KB Output is correct
30 Correct 4135 ms 162164 KB Output is correct
31 Correct 4761 ms 162096 KB Output is correct
32 Correct 949 ms 51352 KB Output is correct
33 Correct 571 ms 53556 KB Output is correct
34 Correct 462 ms 47940 KB Output is correct
35 Correct 517 ms 47932 KB Output is correct
36 Correct 510 ms 47716 KB Output is correct
37 Correct 582 ms 47740 KB Output is correct