oj.uz

Submission #713539

# Submission time Handle Problem Language Result Execution time Memory
713539 2023-03-22T12:15:02 Z Spade1 Factories (JOI14_factories) C++14
15 / 100
 7473 ms 524288 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 != -1) {
        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 != -1) {
        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;
    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: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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 16600 KB Output is correct
2 Correct 3757 ms 28420 KB Output is correct
3 Correct 5978 ms 39536 KB Output is correct
4 Correct 6374 ms 39512 KB Output is correct
5 Correct 7315 ms 41068 KB Output is correct
6 Correct 837 ms 34724 KB Output is correct
7 Correct 6533 ms 39316 KB Output is correct
8 Correct 5758 ms 39624 KB Output is correct
9 Correct 7473 ms 41004 KB Output is correct
10 Correct 862 ms 34772 KB Output is correct
11 Correct 5944 ms 39436 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16340 KB Output is correct
2 Runtime error 6483 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 16600 KB Output is correct
2 Correct 3757 ms 28420 KB Output is correct
3 Correct 5978 ms 39536 KB Output is correct
4 Correct 6374 ms 39512 KB Output is correct
5 Correct 7315 ms 41068 KB Output is correct
6 Correct 837 ms 34724 KB Output is correct
7 Correct 6533 ms 39316 KB Output is correct
8 Correct 5758 ms 39624 KB Output is correct
9 Correct 7473 ms 41004 KB Output is correct
10 Correct 862 ms 34772 KB Output is correct
11 Correct 5944 ms 39436 KB Output is correct
12 Correct 14 ms 16340 KB Output is correct
13 Runtime error 6483 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -