Submission #1284876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284876		trantrungkein	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	310 ms	43184 KiB

election_campaign

#include <bits/stdc++.h>
#define int long long
#define fi           first
#define si           second
#define For(i,a,b)   for (int i = (a), _b =(b); i <= _b; ++i)
#define all(v)       v.begin(), v.end()
#define Unique(v)    v.erase(unique(all(v)), v.end())
#define MASK(i)      (1LL << (i))
#define bit(i,n)     (((n)>>(i)) & 1)
#define Vii          vector<pair<int,int>>
#define setpr(x)     cout<<setprecision(x)<<fixed
#define Prior        priority_queue< pair<int,int> , Vii, greater<Pair> >
using namespace std;

const int Mod = 1E9 + 7;
const long long INF  = 4E18;
const int N = 4e5 + 1;
const int Log = 20;
int dept[N],up[N][Log+2];
int in[N],out[N],Time = 0;
vector<int> g[N];
void dfs_lca(int u, int p)
{
    up[u][0] = p;
    in[u] = ++Time;
    for(int i = 1; i <= Log; i++) up[u][i] = up[up[u][i-1]][i-1];
    for(int v : g[u]) if(v != p)
    {
        dept[v] = dept[u] + 1;
        dfs_lca(v,u);
    }
    out[u] = ++Time;
}
int LCA(int u, int v)
{
    if(dept[u] < dept[v]) swap(u,v);
    int LenK = dept[u] - dept[v];
    for(int i = Log; i >= 0; i--) if(LenK&(1<<i)) u = up[u][i];
    if(u == v) return u;
    for(int i = Log; i >= 0; i--) if(up[u][i] != up[v][i])
    {
        u = up[u][i];
        v = up[v][i];
    }
    return up[u][0];
}

int n,m;
vector<array<int,3>> query[N];
//BIT
int BIT[N];
void update_sum(int id, int val)
{
    for(;id <= 2*n; id += -id&id) BIT[id] += val;
}
int sumBIT(int id)
{
    int sum = 0;
    for(;id > 0; id -= -id&id) sum += BIT[id];
    return sum;
}
int get_sum(int l, int r)
{
    return sumBIT(r)-sumBIT(l-1);
}

int BIT2[N];
void update(int id, int val)
{
    for(;id <= 2*n; id += -id&id) BIT2[id] += val;
}
int sum(int id)
{
    int sum = 0;
    for(;id > 0; id -= -id&id) sum += BIT2[id];
    return sum;
}
int get(int l, int r)
{
    return sum(r)-sum(l-1);
}
int dp[N];
int getpath(int l, int r, int u)
{
    return get_sum(in[u],in[l]) + get_sum(in[u],in[r])  - get(in[u],in[l]) - get(in[u],in[r]) - get_sum(in[u],in[u]) + get(in[u],in[u]);
}
//
void dfs(int u, int p){
    int sum = 0;
    for(int v : g[u]) if(v != p)
    {
        dfs(v,u);
        sum += dp[v];
    }
    dp[u] = sum;
    update_sum(in[u],sum);
    update_sum(out[u],-sum);
    for(auto [l,r,c] : query[u]){
        dp[u] = max(dp[u],getpath(l,r,u) + c);
        //cerr <<"a "<< l << ' '  << r <<' ' << c << endl;
       // cerr << getpath(l,r,u) << endl;
    }
   // cerr << u <<' ' << dp[u] <<' ' << sum <<' ' << endl;
    update(in[u],dp[u]);
    update(out[u],-dp[u]);
}
int32_t main()
{
    cin >> n;
    for(int i = 1; i < n; i++){
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs_lca(1,0);
    cin >> m;
    for(int i = 1; i <= m; i++)
    {   int u,v,c;
        cin >> u >> v >> c;
        int anc = LCA(u,v);
        query[anc].push_back({u,v,c});
    }
    dfs(1,0);
    cout << dp[1];

}

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