Submission #968959

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
968959	2024-04-24T10:22:39 Z	Yang8on	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	115 ms	34636 KB

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

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
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Incorrect	2 ms	10684 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	10588 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	2 ms	10844 KB	Output is correct
4	Correct	93 ms	34052 KB	Output is correct
5	Correct	94 ms	34048 KB	Output is correct
6	Correct	85 ms	34124 KB	Output is correct
7	Correct	95 ms	34100 KB	Output is correct
8	Correct	100 ms	34128 KB	Output is correct
9	Correct	85 ms	34072 KB	Output is correct
10	Correct	94 ms	34020 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	10588 KB	Output is correct
2	Correct	2 ms	10588 KB	Output is correct
3	Correct	2 ms	10844 KB	Output is correct
4	Correct	93 ms	34052 KB	Output is correct
5	Correct	94 ms	34048 KB	Output is correct
6	Correct	85 ms	34124 KB	Output is correct
7	Correct	95 ms	34100 KB	Output is correct
8	Correct	100 ms	34128 KB	Output is correct
9	Correct	85 ms	34072 KB	Output is correct
10	Correct	94 ms	34020 KB	Output is correct
11	Correct	11 ms	11612 KB	Output is correct
12	Correct	95 ms	34440 KB	Output is correct
13	Correct	97 ms	34392 KB	Output is correct
14	Correct	89 ms	34320 KB	Output is correct
15	Correct	96 ms	34636 KB	Output is correct
16	Correct	85 ms	34336 KB	Output is correct
17	Correct	94 ms	34396 KB	Output is correct
18	Correct	93 ms	34388 KB	Output is correct
19	Correct	91 ms	34528 KB	Output is correct
20	Correct	93 ms	34420 KB	Output is correct