oj.uz

Submission #772140

# Submission time Handle Problem Language Result Execution time Memory
772140 2023-07-03T17:01:10 Z Essa2006 Factories (JOI14_factories) C++14
100 / 100
 7520 ms 159436 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>30 && T>30){
        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 40 ms 852 KB Output is correct
2 Correct 420 ms 10264 KB Output is correct
3 Correct 309 ms 10076 KB Output is correct
4 Correct 843 ms 10240 KB Output is correct
5 Correct 363 ms 10220 KB Output is correct
6 Correct 496 ms 10300 KB Output is correct
7 Correct 411 ms 10004 KB Output is correct
8 Correct 651 ms 10132 KB Output is correct
9 Correct 355 ms 10100 KB Output is correct
10 Correct 552 ms 10328 KB Output is correct
11 Correct 304 ms 10076 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 2081 ms 133848 KB Output is correct
3 Correct 5540 ms 131132 KB Output is correct
4 Correct 1325 ms 136752 KB Output is correct
5 Correct 6370 ms 133028 KB Output is correct
6 Correct 3971 ms 133032 KB Output is correct
7 Correct 7520 ms 35276 KB Output is correct
8 Correct 1959 ms 38116 KB Output is correct
9 Correct 5766 ms 37172 KB Output is correct
10 Correct 4676 ms 36632 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 852 KB Output is correct
2 Correct 420 ms 10264 KB Output is correct
3 Correct 309 ms 10076 KB Output is correct
4 Correct 843 ms 10240 KB Output is correct
5 Correct 363 ms 10220 KB Output is correct
6 Correct 496 ms 10300 KB Output is correct
7 Correct 411 ms 10004 KB Output is correct
8 Correct 651 ms 10132 KB Output is correct
9 Correct 355 ms 10100 KB Output is correct
10 Correct 552 ms 10328 KB Output is correct
11 Correct 304 ms 10076 KB Output is correct
12 Correct 4 ms 468 KB Output is correct
13 Correct 2081 ms 133848 KB Output is correct
14 Correct 5540 ms 131132 KB Output is correct
15 Correct 1325 ms 136752 KB Output is correct
16 Correct 6370 ms 133028 KB Output is correct
17 Correct 3971 ms 133032 KB Output is correct
18 Correct 7520 ms 35276 KB Output is correct
19 Correct 1959 ms 38116 KB Output is correct
20 Correct 5766 ms 37172 KB Output is correct
21 Correct 4676 ms 36632 KB Output is correct
22 Correct 1352 ms 142740 KB Output is correct
23 Correct 2485 ms 146344 KB Output is correct
24 Correct 1550 ms 141932 KB Output is correct
25 Correct 2215 ms 142932 KB Output is correct
26 Correct 1795 ms 138300 KB Output is correct
27 Correct 3003 ms 142872 KB Output is correct
28 Correct 1665 ms 159436 KB Output is correct
29 Correct 3664 ms 138324 KB Output is correct
30 Correct 4280 ms 138304 KB Output is correct
31 Correct 5102 ms 138388 KB Output is correct
32 Correct 1133 ms 51132 KB Output is correct
33 Correct 926 ms 53352 KB Output is correct
34 Correct 546 ms 47868 KB Output is correct
35 Correct 587 ms 47936 KB Output is correct
36 Correct 660 ms 47724 KB Output is correct
37 Correct 704 ms 47688 KB Output is correct