oj.uz

답안 #772097

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
772097 2023-07-03T15:55:56 Z Essa2006 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 136652 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];
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
const ll inf=1e15, lg=19;
int n;
vector<ll>Dis;
vector<int>dpth;
vector<vector<int>>BB, AA, up;

inline 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));
}

inline 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);
            }
        }
    }
}
inline 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<=10 && T<=10){
        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;
    }
    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];
            if(D[u]+BB[u][i]<D[v]){
                D[v]=D[u]+BB[u][i];
                q.push({-D[v], v});
            }
        }
    }
}
// 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:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int i=0;i<AA[u].size();i++){
      |                     ~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for(int i=0;i<AA[u].size();i++){
      |                     ~^~~~~~~~~~~~~
factories.cpp:102:23: warning: control reaches end of non-void function [-Wreturn-type]
  102 |     vector<ll>D(n, inf);
      |                       ^
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 8 ms 724 KB Output is correct
2 Correct 291 ms 9608 KB Output is correct
3 Correct 295 ms 9568 KB Output is correct
4 Correct 334 ms 9716 KB Output is correct
5 Correct 282 ms 9584 KB Output is correct
6 Correct 388 ms 9788 KB Output is correct
7 Correct 307 ms 9512 KB Output is correct
8 Correct 929 ms 9784 KB Output is correct
9 Correct 281 ms 9604 KB Output is correct
10 Correct 387 ms 9784 KB Output is correct
11 Correct 291 ms 9524 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 1993 ms 133752 KB Output is correct
3 Correct 5600 ms 131124 KB Output is correct
4 Correct 1270 ms 136652 KB Output is correct
5 Correct 5877 ms 132788 KB Output is correct
6 Correct 3775 ms 132852 KB Output is correct
7 Execution timed out 8060 ms 34628 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 724 KB Output is correct
2 Correct 291 ms 9608 KB Output is correct
3 Correct 295 ms 9568 KB Output is correct
4 Correct 334 ms 9716 KB Output is correct
5 Correct 282 ms 9584 KB Output is correct
6 Correct 388 ms 9788 KB Output is correct
7 Correct 307 ms 9512 KB Output is correct
8 Correct 929 ms 9784 KB Output is correct
9 Correct 281 ms 9604 KB Output is correct
10 Correct 387 ms 9784 KB Output is correct
11 Correct 291 ms 9524 KB Output is correct
12 Correct 4 ms 468 KB Output is correct
13 Correct 1993 ms 133752 KB Output is correct
14 Correct 5600 ms 131124 KB Output is correct
15 Correct 1270 ms 136652 KB Output is correct
16 Correct 5877 ms 132788 KB Output is correct
17 Correct 3775 ms 132852 KB Output is correct
18 Execution timed out 8060 ms 34628 KB Time limit exceeded
19 Halted 0 ms 0 KB -