Submission #1168349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168349		HoriaHaivas	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	223 ms	37660 KiB

election_campaign

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}


int up[100005][17];
int h[100005];

int lca(int a, int b)
{
    if (h[a]<h[b])
        swap(a,b);
    int k,i;
    k=h[a]-h[b];
    for (i=16; i>=0; i--)
    {
        if (k&(1<<i))
            a=up[a][i];
    }
    if (a==b)
        return a;
    for (i=16; i>=0; i--)
    {
        if (up[a][i]!=up[b][i])
        {
            a=up[a][i];
            b=up[b][i];
        }
    }
    return up[a][0];
}

bool is_ancestor(int b, int a)
{
    int k,i;
    k=h[a]-h[b];
    for (i=16; i>=0; i--)
    {
        if (k&(1<<i))
            a=up[a][i];
    }
    if (a==b)
        return 1;
    return 0;
}

struct idk
{
    int a;
    int b;
    int c;
};

vector<int> nodes[100005];
vector<idk> paths[100005];
int dp[100005];
int tin[100005];
int tout[100005];
int timer;

class AIB
{
public:
    int aib[200005];
    void setval(int node, int val)
    {
        update(tin[node],val);
        update(tout[node]+1,-val);
    }
    void update(int idx, int val)
    {
        while (idx<=timer)
        {
            aib[idx]+=val;
            idx+=idx&(-idx);
        }
    }
    int query(int idx)
    {
        int ans;
        ans=0;
        while(idx>0)
        {
            ans+=aib[idx];
            idx-=idx&(-idx);
        }
        return ans;
    }
    int query(int a, int b)
    {
        int ans,meet;
        ans=0;
        meet=lca(a,b);
        ans+=query(tin[a]);
        ans+=query(tin[b]);
        ans-=query(tin[meet]);
        return ans;
    }
} aib;

void dfs(int node, int parent)
{
    timer++;
    tin[node]=timer;
    up[node][0]=parent;
    for (auto x : nodes[node])
    {
        if (x!=parent)
        {
            h[x]=h[node]+1;
            dfs(x,node);
        }
    }
    timer++;
    tout[node]=timer;
}

void calcdp(int node, int parent)
{
    int childsum;
    childsum=0;
    for (auto x : nodes[node])
    {
        if (x!=parent)
        {
            calcdp(x,node);
            childsum+=dp[x];
        }
    }
    for (auto x : paths[node])
    {
        dp[node]=max(dp[node],x.c+aib.query(x.a,x.b)+childsum);
    }
    dp[node]=max(dp[node],childsum);
    aib.setval(node,childsum-dp[node]);
}

signed main()
{
    //ifstream fin("sirbun.in");
    //ofstream fout("sirbun.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,i,j,u,v,a,b,c;
    cin >> n;
    for (i=1; i<=n-1; i++)
    {
        cin >> u >> v;
        nodes[u].push_back(v);
        nodes[v].push_back(u);
    }
    timer=0;
    h[1]=1;
    dfs(1,1);
    for (i=1; i<=16; i++)
    {
        for (j=1; j<=n; j++)
        {
            up[j][i]=up[up[j][i-1]][i-1];
        }
    }
    cin >> m;
    for (i=1; i<=m; i++)
    {
        cin >> a >> b >> c;
        paths[lca(a,b)].push_back({a,b,c});
    }
    calcdp(1,1);
    cout << dp[1];
    return 0;
}

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