제출 #945209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
945209		VMaksimoski008	공장들 (JOI14_factories)	C++14	100 / 100	4121 ms	361496 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 5e5 + 5;
const double eps = 1e-9;

int n, del[maxn], sub[maxn];
ll dist[maxn];
vector<vector<pll> > graph(maxn), anc(maxn);

int get_sub(int u, int p) {
    sub[u] = 1;
    for(auto &[v, _] : graph[u]) {
        if(v == p || del[v]) continue;
        sub[u] += get_sub(v, u);
    }
    return sub[u];
}

int get_cen(int u, int p, int sz) {
    for(auto &[v, _] : graph[u]) {
        if(v == p || del[v]) continue;
        if(2 * sub[v] > sz) return get_cen(v, u, sz);
    }
    return u;
}

void get_dist(int u, int cen, int p, ll d) {
    for(auto &[v, w] : graph[u]) {
        if(v == p || del[v]) continue;
        get_dist(v, cen, u, d + w);
    }
    anc[u].push_back({ cen, d });
}

void update(int u, int t) {
    for(auto &[v, d] : anc[u]) {
        if(t) dist[v] = min(dist[v], d);
        else dist[v] = 1e18;
    }
    dist[u] = (t ? 0 : 1e18);
}

ll query(int u) {
    ll ans = dist[u];
    for(auto &[v, d] : anc[u])
        ans = min(ans, d + dist[v]);
    return ans;
}

void build(int u) {
    int cen = get_cen(u, -1, get_sub(u, -1));

    for(auto &[v, w] : graph[cen]) {
        if(del[v]) continue;
        get_dist(v, cen, cen, w);
    }

    del[cen] = 1;

    for(auto &[v, w] : graph[cen]) {
        if(del[v]) continue;
        build(v);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i=0; i<n-1; i++) {
        graph[A[i]].push_back({ B[i], D[i] });
        graph[B[i]].push_back({ A[i], D[i] });
    }
    for(int i=0; i<n; i++) dist[i] = 1e18;
    build(0);
}

ll Query(int S, int X[], int T, int Y[]) {
    ll ans = 1e18;
    for(int i=0; i<S; i++) update(X[i], 1);
    for(int i=0; i<T; i++) ans = min(ans, query(Y[i]));
    for(int i=0; i<S; i++) update(X[i], 0);
    return ans;
}

// int main() {
//     int N, Q;
//     cin >> N >> Q;
//     int A[N-1], B[N-1], D[N-1];

//     for(int i=0; i<N-1; i++) {
//         cin >> A[i] >> B[i] >> D[i];
//     }

//     Init(N, A, B, D);

//     while(Q--) {
//         int S, T;
//         cin >> S >> T;
//         int X[S], Y[T];

//         for(int i=0; i<S; i++) cin >> X[i];
//         for(int i=0; i<T; i++) cin >> Y[i];

//         cout << Query(S, X, T, Y) << '\n';
//     }

//     return 0;
// }

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

factories.cpp: In function 'int get_sub(int, int)':
factories.cpp:27:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for(auto &[v, _] : graph[u]) {
      |               ^
factories.cpp: In function 'int get_cen(int, int, int)':
factories.cpp:35:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |     for(auto &[v, _] : graph[u]) {
      |               ^
factories.cpp: In function 'void get_dist(int, int, int, ll)':
factories.cpp:43:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     for(auto &[v, w] : graph[u]) {
      |               ^
factories.cpp: In function 'void update(int, int)':
factories.cpp:51:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for(auto &[v, d] : anc[u]) {
      |               ^
factories.cpp: In function 'll query(int)':
factories.cpp:60:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     for(auto &[v, d] : anc[u])
      |               ^
factories.cpp: In function 'void build(int)':
factories.cpp:68:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |     for(auto &[v, w] : graph[cen]) {
      |               ^
factories.cpp:75:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |     for(auto &[v, w] : graph[cen]) {
      |               ^

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