oj.uz

답안 #713538

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
713538 2023-03-22T12:06:09 Z Spade1 공장들 (JOI14_factories) C++14
0 / 100
 3457 ms 24396 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], root;

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 dis=0, int prt=-1) {
    mp[{i, root}] = dis;
    mp[{root, i}] = dis;
    for (auto [j, w] : adj[i]) {
        if (j ==prt || mark[j]) continue;
        dfs2(j, dis+w, i);
    }
}

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

    for (auto [j, w] : adj[cen]) {
        if (mark[j]) continue;
        int c = decom(j);
        up[c] = cen;
    }
    return cen;
}

void update(int v) {
    int cur = v;
    while (cur != 0) {
        s.insert(cur);
        mn[cur] = min(mn[cur], mp[{cur, v}]);
        cur = up[cur];
    }
}

ll query(int v) {
    ll ans = INF, cur = v;
    while (cur != 0) {
        ans = min(ans, mn[cur] + mp[{cur, v}]);
        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;
    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:41:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for (auto [j, w] : adj[i]) {
      |               ^
factories.cpp: In function 'int decom(int)':
factories.cpp:53:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |     for (auto [j, w] : adj[cen]) {
      |               ^

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 12688 KB Output is correct
2 Incorrect 3457 ms 24396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 12688 KB Output is correct
2 Incorrect 3457 ms 24396 KB Output isn't correct
3 Halted 0 ms 0 KB -