oj.uz

답안 #945190

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
945190 2024-03-13T13:49:20 Z VMaksimoski008 공장들 (JOI14_factories) C++14
0 / 100
 13 ms 46680 KB 
#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[u]) {
        if(del[v]) continue;
        get_dist(v, cen, cen, w);
    }

    del[cen] = 1;

    for(auto &[v, w] : graph[u]) {
        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;
}

Compilation message

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[u]) {
      |               ^
factories.cpp:75:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |     for(auto &[v, w] : graph[u]) {
      |               ^

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 46680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 46428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 46680 KB Output isn't correct
2 Halted 0 ms 0 KB -