oj.uz

Submission #41000

# Submission time Handle Problem Language Result Execution time Memory
41000 2018-02-11T08:49:19 Z DoanPhuDuc Factories (JOI14_factories) C++
15 / 100
 6000 ms 100368 KB 
#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }

using namespace std;

typedef long long LL;
typedef pair <int, int> II;

const int N = 5e5 + 10;
const LL INF = (LL)1e18;
const int LG = 19;

int n, s, t, q;
int h[N], a[N], b[N], e[N];
int p[N][LG + 2];

LL f[N], d[N];

vector <II> adj[N];

struct CD {
    int cPar[N], c[N];
    void Init() {
        memset(cPar, -1, sizeof cPar);
        DFS(1);
        Centroid(1, -1, c[1], -2);
    }
    void DFS(int u, int par = -1) {
        c[u] = 1;
        REP(k, 0, adj[u].size()) {
            int v = adj[u][k].first; if (v == par || cPar[v] != -1) continue;
            DFS(v, u);
            c[u] += c[v];
        }
    }
    void Centroid(int u, int par, int sz, int preC) {
        REP(k, 0, adj[u].size()) {
            int v = adj[u][k].first; if (v == par || cPar[v] != -1) continue;
            if (c[v] * 2 > sz) {
                Centroid(v, u, sz, preC);
                return;
            }
        }
        cPar[u] = preC;
        REP(k, 0, adj[u].size()) {
            int v = adj[u][k].first; if (cPar[v] != -1) continue;
            DFS(v, u);
            Centroid(v, u, c[v], u);
        }
    }
} CD;

void DFS(int u) {
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k].first, w = adj[u][k].second;
        if (v == p[u][0]) continue;
        p[v][0] = u; d[v] = d[u] + w;
        h[v] = h[u] + 1;
        DFS(v);
    }
}

void InitLCA() {
    for (int j = 1; 1 << j <= n; ++j)
        FOR(i, 1, n) p[i][j] = p[p[i][j - 1]][j - 1];
}

int LCA(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    FOD(i, 19, 0) if (h[u] - (1 << i) >= h[v]) u = p[u][i];
    if (u == v) return u;
    FOD(i, 19, 0) if (p[u][i] != p[v][i]) {
        u = p[u][i];
        v = p[v][i];
    }
    return p[u][0];
}

LL Dist(int u, int v) {
    int w = LCA(u, v);
    return d[u] + d[v] - 2LL * d[w];
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    REP(i, 0, n - 1) {
        int u = A[i], v = B[i], w = D[i];
        ++u; ++v;
        adj[u].push_back(II(v, w));
        adj[v].push_back(II(u, w));
    }
    FOR(i, 1, n) f[i] = INF;
    DFS(1);
    InitLCA();
    CD.Init();
}

void Update(int u) {
    int x = u;
    while (x != -2) {
        f[x] = min(f[x], Dist(x, u));
        x = CD.cPar[x];
    }
}

void Assign(int u, LL v) {
    int x = u;
    while (x != -2) {
        f[x] = v;
        x = CD.cPar[x];
    }
}

LL Query(int u) {
    int x = u; LL ans = INF;
    while (x != -2) {
        ans = min(ans, f[x] + Dist(x, u));
        x = CD.cPar[x];
    }
    return ans;
}

long long Query(int S, int X[], int T, int Y[]) {
    s = S; t = T;
    LL ans = INF;
    REP(i, 0, s) ++X[i];
    REP(i, 0, t) ++Y[i];
    REP(i, 0, s) Update(X[i]);
    REP(i, 0, t) ans = min(ans, Query(Y[i]));
    REP(i, 0, s) Assign(X[i], INF);
    return ans;
}

Compilation message

factories.cpp: In member function 'void CD::DFS(int, int)':
factories.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
factories.cpp:36:9: note: in expansion of macro 'REP'
         REP(k, 0, adj[u].size()) {
         ^
factories.cpp: In member function 'void CD::Centroid(int, int, int, int)':
factories.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
factories.cpp:43:9: note: in expansion of macro 'REP'
         REP(k, 0, adj[u].size()) {
         ^
factories.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
factories.cpp:51:9: note: in expansion of macro 'REP'
         REP(k, 0, adj[u].size()) {
         ^
factories.cpp: In function 'void DFS(int)':
factories.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
factories.cpp:60:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 14456 KB Output is correct
2 Correct 1151 ms 23068 KB Output is correct
3 Correct 2363 ms 23308 KB Output is correct
4 Correct 2296 ms 23392 KB Output is correct
5 Correct 2939 ms 23392 KB Output is correct
6 Correct 455 ms 23392 KB Output is correct
7 Correct 2315 ms 23392 KB Output is correct
8 Correct 2403 ms 23472 KB Output is correct
9 Correct 2820 ms 23472 KB Output is correct
10 Correct 456 ms 23472 KB Output is correct
11 Correct 2309 ms 23556 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23556 KB Output is correct
2 Correct 3960 ms 98928 KB Output is correct
3 Execution timed out 6009 ms 98928 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6039 ms 100368 KB Time limit exceeded
2 Halted 0 ms 0 KB -