oj.uz

답안 #270635

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
270635 2020-08-17T20:33:01 Z MKopchev 공장들 (JOI14_factories) C++14
0 / 100
 8000 ms 112780 KB 
#include "factories.h"
#include<bits/stdc++.h>

#define MAX_N          500000
#define MAX_Q          100000
#define MAX_SUM_ST    1000000
#define MAX_VALUE  1000000000

using namespace std;
const int nmax=5e5+42;

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];

int n;

vector< pair<int/*to*/,int/*cost*/> > adj[nmax];

int height[nmax];

long long depth[nmax];

int up[20][nmax];

void dfs(int node,int par,int h,long long sum)
{
    height[node]=h;
    depth[node]=sum;

    up[0][node]=par;
    for(int i=1;i<20;i++)up[i][node]=up[i-1][up[i-1][node]];

    for(auto k:adj[node])
        if(k.first!=par)
            dfs(k.first,node,h+1,sum+k.second);
}
void Init(int N, int A[], int B[], int D[]) {
    n=N;

    for(int i=0;i<n-1;i++)
    {
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }

    dfs(0,0,0,0);
}

int LCA(int u,int v)
{
    if(height[u]<height[v])swap(u,v);

    for(int i=19;i>=0;i--)
        if(height[u]-(1<<i)>=height[v])u=up[i][u];

    if(u==v)return u;

    for(int i=19;i>=0;i--)
        if(up[i][u]!=up[i][v])u=up[i][u],v=up[i][v];

    return up[0][u];
}
long long dist(int u,int v)
{
    return depth[u]+depth[v]-2*depth[LCA(u,v)];
}
long long Query(int S, int X[], int T, int Y[])
{
    long long ret=1e18;

    for(int i=0;i<S;i++)
        for(int j=0;j<T;j++)
            ret=min(ret,dist(X[i],Y[j]));

    return ret;
}

Compilation message

factories.cpp:20:12: warning: 'Qy' defined but not used [-Wunused-variable]
   20 | static int Qy[MAX_N];
      |            ^~
factories.cpp:19:12: warning: 'Qx' defined but not used [-Wunused-variable]
   19 | static int Qx[MAX_N];
      |            ^~
factories.cpp:17:12: warning: 'Y' defined but not used [-Wunused-variable]
   17 | static int Y[MAX_SUM_ST];
      |            ^
factories.cpp:16:12: warning: 'X' defined but not used [-Wunused-variable]
   16 | static int X[MAX_SUM_ST];
      |            ^
factories.cpp:15:12: warning: 'T' defined but not used [-Wunused-variable]
   15 | static int T[MAX_N];
      |            ^
factories.cpp:14:12: warning: 'S' defined but not used [-Wunused-variable]
   14 | static int S[MAX_N];
      |            ^
factories.cpp:13:32: warning: 'D' defined but not used [-Wunused-variable]
   13 | static int A[MAX_N], B[MAX_N], D[MAX_N];
      |                                ^
factories.cpp:13:22: warning: 'B' defined but not used [-Wunused-variable]
   13 | static int A[MAX_N], B[MAX_N], D[MAX_N];
      |                      ^
factories.cpp:13:12: warning: 'A' defined but not used [-Wunused-variable]
   13 | static int A[MAX_N], B[MAX_N], D[MAX_N];
      |            ^
factories.cpp:12:15: warning: 'Q' defined but not used [-Wunused-variable]
   12 | static int N, Q;
      |               ^
factories.cpp:12:12: warning: 'N' defined but not used [-Wunused-variable]
   12 | static int N, Q;
      |            ^

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 12800 KB Output is correct
2 Execution timed out 8083 ms 21624 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12416 KB Output is correct
2 Correct 2808 ms 88768 KB Output is correct
3 Correct 6800 ms 90216 KB Output is correct
4 Correct 1563 ms 89444 KB Output is correct
5 Correct 5293 ms 112780 KB Output is correct
6 Correct 5233 ms 91464 KB Output is correct
7 Execution timed out 8058 ms 35824 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 12800 KB Output is correct
2 Execution timed out 8083 ms 21624 KB Time limit exceeded
3 Halted 0 ms 0 KB -