oj.uz

답안 #772103

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
772103 2023-07-03T16:01:07 Z Essa2006 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 122772 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+=2){
            int v=AA[u][i], w=AA[u][i+1];
            if(dpth[u]+1<dpth[v]){
                dpth[v]=dpth[u]+1, Dis[v]=Dis[u]+w;
                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);
        AA[u].push_back(w);
        AA[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;
    }
    else{
        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+=2){
                int v=AA[u][i], w=AA[u][i+1];
                if(D[u]+w<D[v]){
                    D[v]=D[u]+w;
                    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+=2){
      |                     ~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:121:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |             for(int i=0;i<AA[u].size();i+=2){
      |                         ~^~~~~~~~~~~~~
factories.cpp:130:1: warning: control reaches end of non-void function [-Wreturn-type]
  130 | }
      | ^
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 12 ms 904 KB Output is correct
2 Correct 298 ms 9780 KB Output is correct
3 Correct 286 ms 9556 KB Output is correct
4 Correct 638 ms 9676 KB Output is correct
5 Correct 294 ms 9560 KB Output is correct
6 Correct 407 ms 9756 KB Output is correct
7 Correct 325 ms 9544 KB Output is correct
8 Correct 483 ms 9576 KB Output is correct
9 Correct 291 ms 9636 KB Output is correct
10 Correct 397 ms 9752 KB Output is correct
11 Correct 289 ms 9508 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 1939 ms 120028 KB Output is correct
3 Correct 5077 ms 117724 KB Output is correct
4 Correct 1147 ms 122772 KB Output is correct
5 Correct 5639 ms 117272 KB Output is correct
6 Correct 3570 ms 119556 KB Output is correct
7 Execution timed out 8055 ms 32000 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 904 KB Output is correct
2 Correct 298 ms 9780 KB Output is correct
3 Correct 286 ms 9556 KB Output is correct
4 Correct 638 ms 9676 KB Output is correct
5 Correct 294 ms 9560 KB Output is correct
6 Correct 407 ms 9756 KB Output is correct
7 Correct 325 ms 9544 KB Output is correct
8 Correct 483 ms 9576 KB Output is correct
9 Correct 291 ms 9636 KB Output is correct
10 Correct 397 ms 9752 KB Output is correct
11 Correct 289 ms 9508 KB Output is correct
12 Correct 4 ms 468 KB Output is correct
13 Correct 1939 ms 120028 KB Output is correct
14 Correct 5077 ms 117724 KB Output is correct
15 Correct 1147 ms 122772 KB Output is correct
16 Correct 5639 ms 117272 KB Output is correct
17 Correct 3570 ms 119556 KB Output is correct
18 Execution timed out 8055 ms 32000 KB Time limit exceeded
19 Halted 0 ms 0 KB -