제출 #780036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
780036		cheat_when_I_was_young	Factories (JOI14_factories)	C++17	0 / 100	9 ms	12500 KiB

factories

#include "factories.h"
#include "bits/stdc++.h"
using namespace std;

const int NM = 5e5 + 5;

int in[NM], d[NM], h[NM];
vector<int> tour;
vector<pair<int,int>> adj[NM];

void dfs(int u, int par) {
    in[u] = tour.size();
    tour.push_back(u);
    for (auto &vv: adj[u]) {
        int v = vv.first, w = vv.second;
        if (v == par) continue;
        d[v] = d[u] + w;
        h[v] = h[u] + 1;
        dfs(v, u);
    }
    tour.push_back(u);
}

const int LG = __lg(NM) + 1;

pair<int,int> ST[LG][NM];

void build() {
    for (int i = 0; i < tour.size(); ++i)
        ST[0][i] = {h[tour[i]], tour[i]};
    for (int j = 1; j < LG; ++j)
        for (int i = 0; i + (1<<j) - 1 < tour.size(); ++i)
            ST[j][i] = min(ST[j-1][i], ST[j-1][i + (1<<(j-1))]);
}

int lca(int l, int r) {
    int k = __lg(r - l + 1);
    return min(ST[k][l], ST[k][r - (1<<k) + 1]).second;
}

void Init(int N, int A[], int B[], int D[]) {
    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(1, 1);
    build();
}

long long Query(int S, int X[], int T, int Y[]) {
    return 0;
}

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

factories.cpp: In function 'void build()':
factories.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < tour.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
factories.cpp:32:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int i = 0; i + (1<<j) - 1 < tour.size(); ++i)
      |                         ~~~~~~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67