제출 #270635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
270635		MKopchev	공장들 (JOI14_factories)	C++14	0 / 100	8083 ms	112780 KiB

factories

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67