oj.uz

Submission #413419

# Submission time Handle Problem Language Result Execution time Memory
413419 2021-05-28T17:06:35 Z souvenir_vayne Factories (JOI14_factories) C++14
15 / 100
 8000 ms 111832 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;
    if(s <= t) {
        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]);
    }
    else {
        for(int i = 0; i < t; i++)
            update(y[i]);
        for(int i = 0; i < s; i++)
            ans = min(ans, query(x[i]));
        for(int i = 0; i < t; i++)
            reset(y[i]);
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 12364 KB Output is correct
2 Correct 1160 ms 20952 KB Output is correct
3 Correct 2155 ms 21220 KB Output is correct
4 Correct 2123 ms 21200 KB Output is correct
5 Correct 2646 ms 21240 KB Output is correct
6 Correct 435 ms 20940 KB Output is correct
7 Correct 2210 ms 21208 KB Output is correct
8 Correct 2240 ms 21096 KB Output is correct
9 Correct 2661 ms 21492 KB Output is correct
10 Correct 453 ms 21104 KB Output is correct
11 Correct 2116 ms 21196 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12264 KB Output is correct
2 Correct 3594 ms 109292 KB Output is correct
3 Execution timed out 8048 ms 111832 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 12364 KB Output is correct
2 Correct 1160 ms 20952 KB Output is correct
3 Correct 2155 ms 21220 KB Output is correct
4 Correct 2123 ms 21200 KB Output is correct
5 Correct 2646 ms 21240 KB Output is correct
6 Correct 435 ms 20940 KB Output is correct
7 Correct 2210 ms 21208 KB Output is correct
8 Correct 2240 ms 21096 KB Output is correct
9 Correct 2661 ms 21492 KB Output is correct
10 Correct 453 ms 21104 KB Output is correct
11 Correct 2116 ms 21196 KB Output is correct
12 Correct 10 ms 12264 KB Output is correct
13 Correct 3594 ms 109292 KB Output is correct
14 Execution timed out 8048 ms 111832 KB Time limit exceeded
15 Halted 0 ms 0 KB -