Submission #40974

#	Time	Username	Problem	Language	Result	Execution time	Memory
40974		DoanPhuDuc	Factories (JOI14_factories)	C++98	33 / 100	6047 ms	190224 KiB

factories

#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;

int n, timer = 0, q, s, t;
int sz[N], x[N], y[N], c[N], p[N], V[N], headChain[N];
int a[N], b[N], e[N];

LL d[N];

vector <II> adj[N];

struct Node {
    LL s0, s1, s2;
    Node () {}
    Node (LL s0, LL s1, LL s2) : s0(s0), s1(s1), s2(s2) {}
};

struct SegmentTree {
    #define m ((l + r) >> 1)
    Node st[4 * N];
    LL lp[4 * N];
    bool rst[4 * N];
    void Merge(int k) {
        st[k].s0 = min(st[k << 1].s0, st[k << 1 | 1].s0);
        st[k].s1 = min(st[k << 1].s1, st[k << 1 | 1].s1);
        st[k].s2 = min(st[k << 1].s2, st[k << 1 | 1].s2);
    }
    void Build(int k, int l, int r) {
        lp[k] = INF;
        if (l == r) {
            int u = V[l];
            st[k] = Node(-2LL * d[u], INF, INF);
            return;
        }
        Build(k << 1, l, m);
        Build(k << 1 | 1, m + 1, r);
        Merge(k);
    }
    void RS(int k) {
        if (rst[k] == false) return;
        rst[k] = false;
        rst[k << 1] = true; rst[k << 1 | 1] = true;
        st[k << 1].s1 = st[k << 1].s2 = INF;
        st[k << 1 | 1].s1 = st[k << 1 | 1].s2 = INF;
        lp[k << 1] = INF; lp[k << 1 | 1] = INF;
    }
    void Propagate(int k) {
        if (lp[k] >= INF) return;
        LL v = lp[k]; lp[k] = INF;
        lp[k << 1] = min(lp[k << 1], v); lp[k << 1 | 1] = min(lp[k << 1 | 1], v);
        st[k << 1].s1 = min(st[k << 1].s1, v);
        st[k << 1 | 1].s1 = min(st[k << 1 | 1].s1, v);
        st[k << 1].s2 = min(st[k << 1].s2, st[k << 1].s0 + v);
        st[k << 1 | 1].s2 = min(st[k << 1 | 1].s2, st[k << 1 | 1].s0 + v);
    }
    void Update(int k, int l, int r, int i, int j, LL v) {
        if (l > j || r < i) return;
        if (i <= l && r <= j) {
            lp[k] = min(lp[k], v);
            st[k].s1 = min(st[k].s1, v);
            st[k].s2 = min(st[k].s2, st[k].s0 + v);
            return;
        }
        RS(k);
        Propagate(k);
        Update(k << 1, l, m, i, j, v);
        Update(k << 1 | 1, m + 1, r, i, j, v);
        Merge(k);
    }
    LL Query(int k, int l, int r, int i, int j) {
        if (l > j || r < i) return INF;
        if (i <= l && r <= j) return st[k].s2;
        RS(k);
        Propagate(k);
        LL ans = min(Query(k << 1, l, m, i, j), Query(k << 1 | 1, m + 1, r, i, j));
        Merge(k);
        return ans;
    }
    void Reset(int k, int l, int r, int i, int j) {
        if (l > j || r < i) return;
        if (i <= l && r <= j) {
            rst[k] = true;
            lp[k] = INF;
            st[k].s1 = st[k].s2 = INF;
            return;
        }
        RS(k);
        Reset(k << 1, l, m, i, j);
        Reset(k << 1 | 1, m + 1, r, i, j);
        Merge(k);
    }
    #undef m
} ST;

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

void HLD(int u, int par) {
    sz[par]++; x[u] = ++timer; V[timer] = u;
    headChain[u] = par;
    int vtx = 0;
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k].first, w = adj[u][k].second; if (v == p[u]) continue;
        if (vtx == 0 || c[vtx] < c[v]) vtx = v;
    }
    if (vtx != 0) HLD(vtx, par);
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k].first; if (v == p[u] || v == vtx) continue;
        HLD(v, v);
    }
    y[u] = timer;
}

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));
    }
    DFS(1);
    HLD(1, 1);
    ST.Build(1, 1, n);
}

void Update(int u, LL v) {
    int a = 1;
    int uChain = headChain[u], aChain = headChain[a];
    while (true) {
        if (aChain == uChain) {
            ST.Update(1, 1, n, x[a], x[u], v);
            break;
        }
        ST.Update(1, 1, n, x[uChain], x[u], v);
        u = uChain; u = p[u];
        uChain = headChain[u];
    }
}

void Reset(int u) {
    int a = 1;
    int uChain = headChain[u], aChain = headChain[a];
    while (true) {
        if (aChain == uChain) {
            ST.Reset(1, 1, n, x[a], x[u]);
            break;
        }
        ST.Reset(1, 1, n, x[uChain], x[u]);
        u = uChain; u = p[u];
        uChain = headChain[u];
    }
}

LL Query(int u) {
    LL w = d[u];
    int a = 1;
    int uChain = headChain[u], aChain = headChain[a];
    LL ans = INF;
    while (true) {
        if (aChain == uChain) {
            ans = min(ans, ST.Query(1, 1, n, x[a], x[u]));
            break;
        }
        ans = min(ans, ST.Query(1, 1, n, x[uChain], x[u]));
        u = uChain; u = p[u];
        uChain = headChain[u];
    }
    return ans + w;
}

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

Compilation message (stderr)

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:111:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
factories.cpp: In function 'void HLD(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:123:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
factories.cpp:124:34: warning: unused variable 'w' [-Wunused-variable]
         int v = adj[u][k].first, w = adj[u][k].second; if (v == p[u]) continue;
                                  ^
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:128:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 0 / 67