oj.uz

Submission #413414

# Submission time Handle Problem Language Result Execution time Memory
413414 2021-05-28T16:57:55 Z souvenir_vayne Factories (JOI14_factories) C++14
15 / 100
 8000 ms 172116 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, int> pii;

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

ll 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];
}

ll 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) {
    ll aux = u, 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 30 ms 12364 KB Output is correct
2 Correct 1217 ms 21476 KB Output is correct
3 Correct 2256 ms 30996 KB Output is correct
4 Correct 2233 ms 31148 KB Output is correct
5 Correct 2840 ms 31388 KB Output is correct
6 Correct 439 ms 30952 KB Output is correct
7 Correct 2249 ms 31176 KB Output is correct
8 Correct 2368 ms 31028 KB Output is correct
9 Correct 2856 ms 31160 KB Output is correct
10 Correct 440 ms 30788 KB Output is correct
11 Correct 2243 ms 30996 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 3904 ms 153296 KB Output is correct
3 Execution timed out 8013 ms 172116 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12364 KB Output is correct
2 Correct 1217 ms 21476 KB Output is correct
3 Correct 2256 ms 30996 KB Output is correct
4 Correct 2233 ms 31148 KB Output is correct
5 Correct 2840 ms 31388 KB Output is correct
6 Correct 439 ms 30952 KB Output is correct
7 Correct 2249 ms 31176 KB Output is correct
8 Correct 2368 ms 31028 KB Output is correct
9 Correct 2856 ms 31160 KB Output is correct
10 Correct 440 ms 30788 KB Output is correct
11 Correct 2243 ms 30996 KB Output is correct
12 Correct 10 ms 12236 KB Output is correct
13 Correct 3904 ms 153296 KB Output is correct
14 Execution timed out 8013 ms 172116 KB Time limit exceeded
15 Halted 0 ms 0 KB -