oj.uz

답안 #713570

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
713570 2023-03-22T13:59:34 Z Spade1 공장들 (JOI14_factories) C++14
0 / 100
 20 ms 16312 KB 
#include <bits/stdc++.h>
#include "factories.h"
//#include "grader.cpp"
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define pb push_back
#define INF 1e18
using namespace std;

const int maxN = 500050;

vector<pll> adj[maxN];
map<pll, ll> mp;
set<ll> s;
bool mark[maxN];
ll sz[maxN], mn[maxN], up[maxN], dist[maxN], updist[maxN];

int dfs(int i, int prt=-1) {
    sz[i] = 1;
    for (auto [j, w] : adj[i]) {
        if (j == prt || mark[j]) continue;
        sz[i] += dfs(j, i);
    }
    return sz[i];
}

int find_centroid(int i, int m, int prt=-1) {
    for (auto [j, w] : adj[i]) {
        if (j == prt || mark[j]) continue;
        if (sz[j] > m/2) return find_centroid(j, m, i);
    }
    return i;
}

void dfs2(int i, ll cur=0, int prt=-1) {
    dist[i] = cur;
    for (auto [j, w] : adj[i]) {
        if (j == prt || mark[j]) continue;
        dfs2(j, cur+w, i);
    }
}

int decom(int x=0) {
    int cen = find_centroid(x, dfs(x));
    mark[cen] = 1;

    vector<int> v;
    for (auto [j, w] : adj[cen]) {
        if (mark[j]) continue;
        int c = decom(j);
        up[c] = cen;
        v.pb(c);
    }
    dfs2(cen);
    for (int i = 0; i < v.size(); ++i) {
        if (mark[v[i]]) continue;
        updist[v[i]] = dist[v[i]];
    }
    mark[cen] = 0;
    return cen;
}

void update(int v) {
    int cur = v;
    ll dis = 0;
    while (cur != -1) {
        s.insert(cur);
        mn[cur] = min(mn[cur], dis);
        dis += updist[cur];
        cur = up[cur];
    }
}

ll query(int v) {
    ll ans = INF, cur = v, dis = 0;
    while (cur != -1) {
        ans = min(ans, mn[cur] + dis);
        dis += updist[cur];
        cur = up[cur];
    }
    return ans;
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N-1; ++i) {
        adj[A[i]].pb({B[i], D[i]});
        adj[B[i]].pb({A[i], D[i]});
    }
    for (int i = 0; i < N; ++i) mn[i] = INF;
    memset(up, -1, sizeof(up));
    decom();
}

ll Query(int S, int X[], int T, int Y[]) {
    s.clear();
    for (int i = 0; i < S; ++i) update(X[i]);
    ll ans = INF;
    for (int i = 0; i < T; ++i) ans = min(ans, query(Y[i]));
    for (auto i : s) mn[i] = INF;
    return ans;
}

Compilation message

factories.cpp: In function 'int dfs(int, int)':
factories.cpp:23:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for (auto [j, w] : adj[i]) {
      |               ^
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:31:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for (auto [j, w] : adj[i]) {
      |               ^
factories.cpp: In function 'void dfs2(int, long long int, int)':
factories.cpp:40:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for (auto [j, w] : adj[i]) {
      |               ^
factories.cpp: In function 'int decom(int)':
factories.cpp:51:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for (auto [j, w] : adj[cen]) {
      |               ^
factories.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < v.size(); ++i) {
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

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