Submission #378382

#	Time	Username	Problem	Language	Result	Execution time	Memory
378382		mihai145	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	265 ms	49248 KiB

election_campaign

#include <iostream>
#include <vector>

using namespace std;

const int NMAX = 1e5;
const int LGMAX = 17;

int N, M;
vector <int> g[NMAX + 2], gNoDad[NMAX + 2];

int kTime, timeIn[NMAX + 2], timeOut[NMAX + 2];
int h[NMAX + 2], dad[NMAX + 2], w[NMAX + 2];

int log2[2 * NMAX + 2], firstAp[NMAX + 2];
vector <int> rmq[LGMAX + 2];

void dfs(int node, int parent = 0) {
    dad[node] = parent;
    w[node] = 1;

    ++kTime;
    timeIn[node] = kTime;

    firstAp[node] = (int)rmq[0].size();
    rmq[0].push_back(node);

    for(int son : g[node]) {
        if(son != parent) {
            h[son] = h[node] + 1;
            gNoDad[node].push_back(son);
            dfs(son, node);
            w[node] += w[son];
            rmq[0].push_back(node);
        }
    }

    timeOut[node] = kTime;
}

int getMin(int x, int y) {
    if(h[x] < h[y]) {
        return x;
    }

    return y;
}

void buildRmq() {
    for(int i = 2; i <= 2 * N; i++) {
        log2[i] = log2[i / 2] + 1;
    }

    for(int i = 1; i <= LGMAX; i++) {
        if((1 << i) > (int)rmq[0].size()) {
            return ;
        }

        for(int j = 0; j < (int)rmq[0].size(); j++) {
            if((1 << i) + j > (int)rmq[0].size()) {
                break;
            } else {
                rmq[i].push_back(getMin(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]));
            }
        }
    }
}

int queryRmq(int x, int y) {
    x = firstAp[x];
    y = firstAp[y];

    if(x > y) {
        swap(x, y);
    }

    int k = log2[y - x + 1];

    return getMin(rmq[k][x], rmq[k][y - (1 << k) + 1]);
}

vector <int> heavyOrder;
int head[NMAX + 2], pos[NMAX + 2], hs[NMAX + 2];

void dfsHeavy(int node, int heavyHead) {
    head[node] = heavyHead;
    heavyOrder.push_back(node);
    pos[node] = (int)heavyOrder.size();

    int heavySon = g[node][0];
    if(g[node].size() == 1) {
        if(g[node][0] == dad[node]) {
            return ;
        }
    } else {
        if(g[node][0] == dad[node]) {
            heavySon = g[node][1];
        }
    }

    for(int son : g[node]) {
        if(son != dad[node]) {
            if(w[son] > w[heavySon]) {
                heavySon = son;
            }
        }
    }

    hs[node] = heavySon;
    dfsHeavy(heavySon, heavyHead);

    for(int son : g[node]) {
        if(son != dad[node] && son != heavySon) {
            dfsHeavy(son, son);
        }
    }
}

int dp[NMAX + 2];

struct Road {
    int x, y, c;
};
vector <Road> roads[NMAX + 2];

struct Fenwick {
    int v[NMAX + 2];

    inline int LSB(int x) {
        return x & (-x);
    }

    void Update(int pos, int val) {
        for(int i = pos; i <= N; i += LSB(i)) {
            v[i] += val;
        }
    }

    int Sum(int pos) {
        if(pos <= 0) {
            return 0;
        }

        int ans = 0;
        for(int i = pos; i > 0; i -= LSB(i)) {
            ans += v[i];
        }

        return ans;
    }

    int Query(int st, int dr) {
        return Sum(dr) - Sum(st - 1);
    }
};
Fenwick aib;

int qr(int x, int y) {
    if(head[x] == head[y]) {
        if(pos[x] > pos[y]) {
            swap(x, y);
        }
        return aib.Query(pos[x], pos[y]);
    }

    if(h[head[x]] < h[head[y]]) {
        swap(x, y);
    }

    int ans = qr(dad[head[x]], y);
    if(pos[x] > pos[head[x]]) {
        ans += aib.Query(pos[head[x]], pos[x]);
    } else {
        ans += aib.Query(pos[x], pos[head[x]]);
    }

    x = head[x];
    ans -= dp[x];
    ans += dp[hs[dad[x]]];

    return ans;
}

void solve(int node, int parent = 0) {
    int sumDpSons = 0;
    for(int son : g[node]) {
        if(son != parent) {
            solve(son, node);
            sumDpSons += dp[son];
        }
    }

    dp[node] = sumDpSons;

    for(Road road : roads[node]) {
        int newDp = road.c;
        pair <int, int> miss = {0, 0};

        if(node != road.x) {
            int st = 0, dr = (int)gNoDad[node].size() - 1, sol = -1;

            while(st <= dr) {
                int mid = (st + dr) >> 1;
                int trg = gNoDad[node][mid];

                if(timeIn[trg] <= timeIn[road.x] && timeOut[road.x] <= timeOut[trg]) {
                    sol = trg;
                    break;
                }

                if(timeIn[trg] > timeOut[road.x]) {
                    dr = mid - 1;
                } else {
                    st = mid + 1;
                }
            }

            miss.first = sol;
            newDp += qr(miss.first, road.x);
            newDp += dp[hs[road.x]];
        }

        if(node != road.y) {
            int st = 0, dr = (int)gNoDad[node].size() - 1, sol = -1;

            while(st <= dr) {
                int mid = (st + dr) >> 1;
                int trg = gNoDad[node][mid];

                if(timeIn[trg] <= timeIn[road.y] && timeOut[road.y] <= timeOut[trg]) {
                    sol = trg;
                    break;
                }

                if(timeIn[trg] > timeOut[road.y]) {
                    dr = mid - 1;
                } else {
                    st = mid + 1;
                }
            }

            miss.second = sol;
            newDp += qr(miss.second, road.y);
            newDp += dp[hs[road.y]];
        }

        newDp = newDp + sumDpSons - dp[miss.first] - dp[miss.second];

        dp[node] = max(dp[node], newDp);
    }

    ///Update for dady!
    if(node != 1) {
        if(head[node] != head[dad[node]]) {
            aib.Update(pos[dad[node]], dp[node]);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for(int i = 1; i < N; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    dfs(1);
    buildRmq();

    dfsHeavy(1, 1);

    cin >> M;

    for(int i = 1; i <= M; i++) {
        int x, y, c;
        cin >> x >> y >> c;

        int lca = queryRmq(x, y);
        roads[lca].push_back({x, y, c});
    }

    solve(1);

    cout << dp[1] << '\n';
    return 0;
}

Compilation message (stderr)

election_campaign.cpp:15:5: warning: built-in function 'log2' declared as non-function [-Wbuiltin-declaration-mismatch]
   15 | int log2[2 * NMAX + 2], firstAp[NMAX + 2];
      |     ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40