oj.uz

Submission #413416

# Submission time Handle Problem Language Result Execution time Memory
413416 2021-05-28T17:00:54 Z souvenir_vayne Factories (JOI14_factories) C++14
15 / 100
 8000 ms 111620 KB 
#include <bits/stdc++.h>
#include "factories.h"
#define pb push_back
#define LINF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<int, ll> pii;

const int MAXN = 5e5+5;
int anc[MAXN][22], al[MAXN], pai[MAXN], sz[MAXN], used[MAXN];
ll h[MAXN], best[MAXN];
vector<pii> g[MAXN];

int getsz(int u, int p) {
    sz[u] = 1;
    for(pii &i : g[u])
        if(i.f != p && !used[i.f])
            sz[u] += getsz(i.f, u);
    return sz[u];
}

int findc(int u, int p, int n) {
    for(pii &i : g[u])
        if(i.f != p && !used[i.f] && sz[i.f] > n/2)
            return findc(i.f, u, n);
    return u;
}

void build(int u, int p) {
    int c = findc(u, -1, getsz(u, -1));
    used[c] = 1;
    pai[c] = p;

    for(pii &i : g[c])
        if(!used[i.f])
            build(i.f, c);
}

void dfs(int u) {

    for(pii &i : g[u])
        if(i.f != anc[u][0]) {
            anc[i.f][0] = u;
            al[i.f] = al[u] + 1;
            h[i.f] = h[u] + i.s;
            dfs(i.f);
        }
}

int getlca(int a, int b) {
    if(al[a] < al[b])
        swap(a, b);
    for(int i = 0; i <= 20; i++)
        if( (1<<i) & (al[b] - al[a]) )
            a = anc[a][i];

    if(a == b)
        return a;

    for(int i = 20; i >= 0; i--)
        if(anc[a][i] != anc[b][i])
            a = anc[a][i], b = anc[b][i];

    return anc[a][0];

}

ll dist(int a, int b) {
    return h[a] + h[b] - 2*h[getlca(a, b)];
}

void update(int u) {
    int aux = u;
    while(u != -1) {
        best[u] = min(best[u], dist(aux, u));
        //debug2(u, best[u]);
        u = pai[u];
    }
}

ll query(int u) {
    int aux = u;
    ll ans = LINF;
    while(u != -1) {
        ans = min(ans, best[u] + dist(aux, u));
        u = pai[u];
    }
    return ans;
}

void reset(int u) {
    while(u != -1) {
        best[u] = LINF;
        u = pai[u];
    }
}

void Init(int n, int a[], int b[], int c[]) {
    for(int i = 0; i < n; i++)
        best[i] = LINF;

    for(int i = 0; i < n-1; i++) {
        g[a[i]].pb({b[i], c[i]});
        g[b[i]].pb({a[i], c[i]});
    }

    dfs(0);
    for(int j = 1; j < 22; j++)
        for(int i = 1; i <= n; i++)
            anc[i][j] = anc[anc[i][j-1]][j-1];
    build(0, -1);
}

ll Query(int s, int x[], int t, int y[]) {

    ll ans = LINF;
    for(int i = 0; i < s; i++)
        update(x[i]);
    for(int i = 0; i < t; i++)
        ans = min(ans, query(y[i]));
    for(int i = 0; i < s; i++)
        reset(x[i]);
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12440 KB Output is correct
2 Correct 1252 ms 21036 KB Output is correct
3 Correct 2134 ms 20972 KB Output is correct
4 Correct 2186 ms 20940 KB Output is correct
5 Correct 2772 ms 21232 KB Output is correct
6 Correct 422 ms 20960 KB Output is correct
7 Correct 2154 ms 21148 KB Output is correct
8 Correct 2329 ms 21012 KB Output is correct
9 Correct 2645 ms 21268 KB Output is correct
10 Correct 427 ms 20928 KB Output is correct
11 Correct 2175 ms 20952 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12236 KB Output is correct
2 Correct 3552 ms 109372 KB Output is correct
3 Execution timed out 8084 ms 111620 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12440 KB Output is correct
2 Correct 1252 ms 21036 KB Output is correct
3 Correct 2134 ms 20972 KB Output is correct
4 Correct 2186 ms 20940 KB Output is correct
5 Correct 2772 ms 21232 KB Output is correct
6 Correct 422 ms 20960 KB Output is correct
7 Correct 2154 ms 21148 KB Output is correct
8 Correct 2329 ms 21012 KB Output is correct
9 Correct 2645 ms 21268 KB Output is correct
10 Correct 427 ms 20928 KB Output is correct
11 Correct 2175 ms 20952 KB Output is correct
12 Correct 10 ms 12236 KB Output is correct
13 Correct 3552 ms 109372 KB Output is correct
14 Execution timed out 8084 ms 111620 KB Time limit exceeded
15 Halted 0 ms 0 KB -