Submission #969120

#	Time	Username	Problem	Language	Result	Execution time	Memory
969120		vjudge1	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	152 ms	34640 KiB

election_campaign

#include <bits/stdc++.h>
#define Y8o "Election Campaign"
#define maxn 100005
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}


int n, Q, cnt;
int h[maxn], cha[maxn][20];
int in[maxn], out[maxn];
vector<int> o[maxn];
struct dl { int u, v, w; }; vector<dl> qr[maxn];

void dfs(int u, int par = -1)
{
    in[u] = ++ cnt;
    for(int v : o[u])
    {
        if(v == par) continue;
        h[v] = h[u] + 1, cha[v][0] = u;
        for(int j = 1; j <= 17; j ++) cha[v][j] = cha[cha[v][j - 1]][j - 1];
        dfs(v, u);
    }
    out[u] = cnt;
}

int lca(int u, int v)
{
    if( h[u] < h[v] ) swap(u, v);
    for(int i = 17; i >= 0; --i) if(h[u] - (1 << i) >= h[v]) u = cha[u][i];
    for(int i = 17; i >= 0; --i) if(cha[u][i] != cha[v][i]) u = cha[u][i], v = cha[v][i];
    return u == v ? u : cha[u][0];
}

struct BIT {
    ll bit[maxn];
    void update(int l, int r, ll val) {
        for(; l < maxn; l += (l & -l)) bit[l] += val;
        for(++r; r < maxn; r += (r & -r)) bit[r] -= val;
    }
    ll get(int x, ll ans = 0) {
        for(; x; x -= (x & -x)) ans += bit[x];
        return ans;
    }
} B[2]; /// dp[u][0] || dp[u][0/1]


ll dp[maxn][2];
void dfs2(int u, int par = -1)
{
    for(int v : o[u]) if(v != par)
    {
        dfs2(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }

    B[0].update(in[u], out[u], dp[u][0]);

    for(dl x : qr[u])
    {
        int u1 = x.u, v1 = x.v, w = x.w;
        if(h[u1] > h[v1]) swap(u1, v1);

        ll best = 0;
        ll val1[] = { B[0].get(in[u1]) - B[0].get(in[u]), B[1].get(in[u1]) - B[1].get(in[u]) };
        ll val2[] = { B[0].get(in[v1]) - B[0].get(in[u]), B[1].get(in[v1]) - B[1].get(in[u]) };

        if(u1 == u)
        {
            best = val2[0] - val2[1] + dp[u][0] + 1ll * w;
        }
        else
        {
            best += val1[0] - val1[1] + dp[u][0];
            best += val2[0] - val2[1] + dp[u][0];
            best -= dp[u][0];
            best += 1ll * w;
        }

        dp[u][1] = max(dp[u][1], best);
    }

    B[1].update(in[u], out[u], max(dp[u][0], dp[u][1]) );
}

void solve()
{
    cin >> n;
    for(int i = 1, u, v; i <= n - 1; i ++)
    {
        cin >> u >> v;
        o[u].push_back(v);
        o[v].push_back(u);
    }

    dfs(1);

    cin >> Q;
    for(int i = 1, u, v, w; i <= Q; i ++)
    {
        cin >> u >> v >> w;
        int par = lca(u, v);
        qr[par].push_back({ u, v, w });
    }

    dfs2(1);

    ll ans = 0;
    for(int i = 1; i <= n; i ++) ans = max({ ans, dp[i][0], dp[i][1] });
    cout << ans;
}


int main()
{
    iof();

    int nTest = 1;
//    cin >> nTest;

    while(nTest --) {
        solve();
    }

    ctime();
    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'void iof()':
election_campaign.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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