oj.uz

Submission #715945

# Submission time Handle Problem Language Result Execution time Memory
715945 2023-03-28T14:25:43 Z BackNoob Factories (JOI14_factories) C++14
100 / 100
 4552 ms 224372 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
 
using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}

int par[mxN];
int sub[mxN];
ll best[mxN];
bool removed[mxN];
vector<pair<int, int>> adj[mxN];
vector<ll> dist[mxN];


int find_sz(int u, int p)
{
    sub[u] = 1;
    for(auto it : adj[u]) {
        int v = it.fi;
        if(v == p || removed[v] == true) continue;
        sub[u] += find_sz(v, u);
    }
    return sub[u];
}

int find_cen(int u, int p, int n)
{
    for(auto it : adj[u]) {
        int v = it.fi;
        if(v == p || removed[v] == true) continue;
        if(sub[v] * 2 > n) return find_cen(v, u, n);
    }
    return u;
}

void dfs(int u, int p, int root, ll cur = 0)
{
    if(u != root) dist[u].pb(cur);
    for(auto it : adj[u]) {
        int v = it.fi;
        int c = it.se;
        if(v == p || removed[v] == true) continue;
        dfs(v, u, root, cur + c);
    }
}

void init_cen(int u, int p)
{
    int n = find_sz(u, -1);
    int cen = find_cen(u, -1, n);

    dfs(cen, -1, cen);

    par[cen] = p;
    removed[cen] = true;
    for(auto it : adj[cen]) {
        int v = it.fi;
        if(removed[v] == true) continue;
        init_cen(v, cen);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0; i < N - 1; i++) {
        int u = A[i];
        int v = B[i];
        int c = D[i];
        adj[u].pb({v, c});
        adj[v].pb({u, c});
    }

    init_cen(0, -1);
    memset(best, 0x3f, sizeof(best));
}

void add(int u, int val)
{
    int x = u;
    if(val > 0) best[x] = 0;
    else best[x] = infll;
    int p = sz(dist[u]) - 1;
    while(par[x] != -1) {
        x = par[x];
        if(val > 0) minimize(best[x], dist[u][p]);
        else best[x] = infll;
        --p;
    }
}

ll getans(int u)
{
    ll res = infll;
    int x = u;
    int p = sz(dist[u]) - 1;
    minimize(res, best[x]);
    while(par[x] != -1) {
        x = par[x];
        minimize(res, best[x] + dist[u][p]);
        --p;
    }
    return res;
}

long long Query(int S, int X[], int T, int Y[]) {
    ll res = infll;
    for(int i = 0; i < S; i++) {
        add(X[i], 1);
    }

    for(int i = 0; i < T; i++) {
        minimize(res, getans(Y[i]));
    }

    for(int i = 0; i < S; i++) {
        add(X[i], -1);
    }
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28244 KB Output is correct
2 Correct 268 ms 45880 KB Output is correct
3 Correct 333 ms 46076 KB Output is correct
4 Correct 321 ms 46004 KB Output is correct
5 Correct 337 ms 46424 KB Output is correct
6 Correct 232 ms 45612 KB Output is correct
7 Correct 294 ms 46252 KB Output is correct
8 Correct 324 ms 46260 KB Output is correct
9 Correct 311 ms 46408 KB Output is correct
10 Correct 242 ms 45548 KB Output is correct
11 Correct 292 ms 46040 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27860 KB Output is correct
2 Correct 2150 ms 144092 KB Output is correct
3 Correct 3286 ms 165552 KB Output is correct
4 Correct 673 ms 98380 KB Output is correct
5 Correct 3908 ms 224372 KB Output is correct
6 Correct 3283 ms 150176 KB Output is correct
7 Correct 1058 ms 71332 KB Output is correct
8 Correct 397 ms 61012 KB Output is correct
9 Correct 1034 ms 75572 KB Output is correct
10 Correct 967 ms 72684 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28244 KB Output is correct
2 Correct 268 ms 45880 KB Output is correct
3 Correct 333 ms 46076 KB Output is correct
4 Correct 321 ms 46004 KB Output is correct
5 Correct 337 ms 46424 KB Output is correct
6 Correct 232 ms 45612 KB Output is correct
7 Correct 294 ms 46252 KB Output is correct
8 Correct 324 ms 46260 KB Output is correct
9 Correct 311 ms 46408 KB Output is correct
10 Correct 242 ms 45548 KB Output is correct
11 Correct 292 ms 46040 KB Output is correct
12 Correct 15 ms 27860 KB Output is correct
13 Correct 2150 ms 144092 KB Output is correct
14 Correct 3286 ms 165552 KB Output is correct
15 Correct 673 ms 98380 KB Output is correct
16 Correct 3908 ms 224372 KB Output is correct
17 Correct 3283 ms 150176 KB Output is correct
18 Correct 1058 ms 71332 KB Output is correct
19 Correct 397 ms 61012 KB Output is correct
20 Correct 1034 ms 75572 KB Output is correct
21 Correct 967 ms 72684 KB Output is correct
22 Correct 2514 ms 126984 KB Output is correct
23 Correct 2677 ms 131444 KB Output is correct
24 Correct 3677 ms 150684 KB Output is correct
25 Correct 3619 ms 154348 KB Output is correct
26 Correct 3779 ms 151456 KB Output is correct
27 Correct 4552 ms 205316 KB Output is correct
28 Correct 850 ms 108556 KB Output is correct
29 Correct 3685 ms 173564 KB Output is correct
30 Correct 3749 ms 173152 KB Output is correct
31 Correct 3828 ms 173556 KB Output is correct
32 Correct 1100 ms 76044 KB Output is correct
33 Correct 378 ms 61556 KB Output is correct
34 Correct 703 ms 65360 KB Output is correct
35 Correct 725 ms 65968 KB Output is correct
36 Correct 913 ms 69720 KB Output is correct
37 Correct 862 ms 69680 KB Output is correct