oj.uz

답안 #772143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
772143 2023-07-03T17:02:43 Z Essa2006 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 136760 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>70 && T>70){
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 892 KB Output is correct
2 Correct 826 ms 10376 KB Output is correct
3 Correct 311 ms 10328 KB Output is correct
4 Correct 1405 ms 10484 KB Output is correct
5 Correct 717 ms 10316 KB Output is correct
6 Correct 894 ms 10556 KB Output is correct
7 Correct 304 ms 10324 KB Output is correct
8 Correct 1464 ms 10356 KB Output is correct
9 Correct 729 ms 10360 KB Output is correct
10 Correct 907 ms 10648 KB Output is correct
11 Correct 301 ms 10320 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 528 KB Output is correct
2 Correct 2157 ms 133860 KB Output is correct
3 Correct 6242 ms 131128 KB Output is correct
4 Correct 1392 ms 136760 KB Output is correct
5 Correct 6554 ms 132860 KB Output is correct
6 Correct 4322 ms 132844 KB Output is correct
7 Execution timed out 8045 ms 34044 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 892 KB Output is correct
2 Correct 826 ms 10376 KB Output is correct
3 Correct 311 ms 10328 KB Output is correct
4 Correct 1405 ms 10484 KB Output is correct
5 Correct 717 ms 10316 KB Output is correct
6 Correct 894 ms 10556 KB Output is correct
7 Correct 304 ms 10324 KB Output is correct
8 Correct 1464 ms 10356 KB Output is correct
9 Correct 729 ms 10360 KB Output is correct
10 Correct 907 ms 10648 KB Output is correct
11 Correct 301 ms 10320 KB Output is correct
12 Correct 4 ms 528 KB Output is correct
13 Correct 2157 ms 133860 KB Output is correct
14 Correct 6242 ms 131128 KB Output is correct
15 Correct 1392 ms 136760 KB Output is correct
16 Correct 6554 ms 132860 KB Output is correct
17 Correct 4322 ms 132844 KB Output is correct
18 Execution timed out 8045 ms 34044 KB Time limit exceeded
19 Halted 0 ms 0 KB -