oj.uz

답안 #26444

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26444 2017-06-30T09:53:58 Z chpipis 공장들 (JOI14_factories) C++11
100 / 100
 4609 ms 200152 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second

typedef long long ll;

const int MAXN = 5e5 + 5;
const int LOGN = 20;

const ll INF = 1e17;

vector<int> tree[MAXN];
vector<pair<int, int> > gr[MAXN];
//int par[MAXN][LOGN], lvl[MAXN];
//ll dist[MAXN];


int lvl[MAXN];
ll dist[MAXN][LOGN];
//unordered_map<int, ll> dist[MAXN];
bool mark[MAXN];
int sz[MAXN], cpar[MAXN], root;
ll ans[MAXN];
//int visit[MAXN];

/*
void init(int u) {
    for (int j = 1; j < LOGN; j++)
        if (par[u][j - 1] != -1)
            par[u][j] = par[par[u][j - 1]][j - 1];
    for (auto v : gr[u])
        if (v.fi != par[u][0]) {
            dist[v.fi] = dist[u] + v.se;
            par[v.fi][0] = u;
            lvl[v.fi] = lvl[u] + 1;
            init(v.fi);
        }
}
*/

void dfs(int u, int p, int dep) {
    sz[u] = 1;
    for (auto v : gr[u])
        if (v.fi != p && !mark[v.fi]) {
            if (dep != -1)
                dist[v.fi][dep] = dist[u][dep] + v.se;
            //dist[v.fi][who] = dist[u][who] + v.se;
            dfs(v.fi, u, dep);
            sz[u] += sz[v.fi];
        }
}

void proc(int u, int p, int dep) {
    ll w = dist[u][dep];
    mark[u] = true;
    for (auto v : gr[u])
        if (v.fi != p && !mark[v.fi]) {
            dist[v.fi][dep] = w + v.se;
            proc(v.fi, u, dep);
        }
}
/*
void init(int u) {
    mark[u] = false;
    //if (del) lvl[u] = -1;
    for (auto v : tree[u]) {
        //if (!del) lvl[v] = lvl[u] + 1;
        init(v);
    }
}
*/
int decompose(int u, int p, const int n, int dep) {
    int mx = -1, big = -1;
    for (auto v : gr[u])
        if (v.fi != p && !mark[v.fi] && sz[v.fi] > mx)
            mx = sz[v.fi], big = v.fi;
    //printf("i am at %d and big child is %d\n", u, big);
    if (2 * mx <= n) {
        mark[u] = true;
        lvl[u] = dep;
        //printf("START OF VISIT OF %d\n", u);
        for (auto v : gr[u])
            if (!mark[v.fi]) {
                //dist[v.fi][u] = v.se;
                dist[v.fi][lvl[u]] = v.se;
                dfs(v.fi, u, lvl[u]);

                int cent = decompose(v.fi, u, sz[v.fi], dep + 1);
                cpar[cent] = u;
                tree[u].pb(cent);

                //lvl[cent] = 1;
                //init(cent, false);

                //init(cent);

                //value++;
                //dist[v.fi][lvl[u]] = v.se;
                //proc(v.fi, u, lvl[u]);

                //init(cent, true);
            }
        //printf("END OF VISIT OF %d\n", u);
        return u;
    } else {
        return decompose(big, u, n, dep);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N - 1; i++) {
        gr[A[i]].pb(mp(B[i], D[i]));
        gr[B[i]].pb(mp(A[i], D[i]));
    }
    /*for (int i = 0; i < N; i++) {
        dist[i].reserve(LOGN);
        dist[i][i] = 0;
    }*/
    //memset(par, -1, sizeof par);
    //init(0);
    memset(cpar, -1, sizeof cpar);
    dfs(0, -1, -1);
    //memset(lvl, -1, sizeof lvl);
    //memset(dist, -1, sizeof dist);
    root = decompose(0, -1, sz[0], 0);
    fill(ans, ans + N + 1, INF);
    /*init(root);
    for (int i = 0; i < N; i++)
        proc(i, i, cpar[i]);*/
    /*printf("centroid is %d\n", root);
    for (int u = 0; u < N; u++)
        printf("cpar[%d] = %d\n", u, cpar[u]);*/
}
/*
unordered_map<int, int> memo[MAXN];

int LCA(int u, int v) {
    if (lvl[u] > lvl[v]) swap(u, v);
    if (memo[u].count(v))
        return memo[u][v];
    int &ret = memo[u][v];
    for (int j = LOGN - 1; j >= 0; j--)
        if (lvl[u] + (1 << j) <= lvl[v])
            v = par[v][j];
    if (u == v) return ret = u;
    for (int j = LOGN - 1; j >= 0; j--)
        if (par[u][j] != -1 && par[u][j] != par[v][j])
            u = par[u][j], v = par[v][j];
    return ret = par[u][0];
}

ll far(int u, int v) {
    int l = LCA(u, v);
    return dist[u] + dist[v] - dist[l] * 2LL;
}
*/
ll Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        int u = X[i], c = lvl[X[i]];
        while (u != -1) {
            ans[u] = min(ans[u], dist[X[i]][c--]);
            u = cpar[u];
        }
    }
    ll res = INF;
    for (int i = 0; i < T; i++) {
        int u = Y[i], c = lvl[Y[i]];
        while (u != -1) {
            res = min(res, dist[Y[i]][c--] + ans[u]);
            u = cpar[u];
        }
    }
    for (int i = 0; i < S; i++) {
        int u = X[i];
        while (u != -1) {
            ans[u] = INF;
            u = cpar[u];
        }
    }
    return res;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 136108 KB Output is correct
2 Correct 429 ms 136372 KB Output is correct
3 Correct 476 ms 136372 KB Output is correct
4 Correct 423 ms 136372 KB Output is correct
5 Correct 446 ms 136668 KB Output is correct
6 Correct 366 ms 136408 KB Output is correct
7 Correct 436 ms 136372 KB Output is correct
8 Correct 489 ms 136372 KB Output is correct
9 Correct 479 ms 136660 KB Output is correct
10 Correct 306 ms 136408 KB Output is correct
11 Correct 399 ms 136372 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 136108 KB Output is correct
2 Correct 1859 ms 161848 KB Output is correct
3 Correct 3019 ms 166920 KB Output is correct
4 Correct 1216 ms 160004 KB Output is correct
5 Correct 4189 ms 200152 KB Output is correct
6 Correct 2989 ms 166276 KB Output is correct
7 Correct 1136 ms 142136 KB Output is correct
8 Correct 586 ms 141360 KB Output is correct
9 Correct 1293 ms 146008 KB Output is correct
10 Correct 1066 ms 141988 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2659 ms 161848 KB Output is correct
2 Correct 2713 ms 161848 KB Output is correct
3 Correct 3433 ms 165444 KB Output is correct
4 Correct 3843 ms 166300 KB Output is correct
5 Correct 3959 ms 166100 KB Output is correct
6 Correct 4609 ms 191484 KB Output is correct
7 Correct 1453 ms 160004 KB Output is correct
8 Correct 3233 ms 165548 KB Output is correct
9 Correct 3496 ms 164756 KB Output is correct
10 Correct 3233 ms 165608 KB Output is correct
11 Correct 1289 ms 146728 KB Output is correct
12 Correct 453 ms 141360 KB Output is correct
13 Correct 813 ms 141256 KB Output is correct
14 Correct 819 ms 141256 KB Output is correct
15 Correct 1029 ms 142000 KB Output is correct
16 Correct 1049 ms 141980 KB Output is correct