Submission #1181331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181331		vnedu	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	124 ms	32584 KiB

election_campaign

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 1e5 + 15;
const int P = 1e5 + 15;

int numNode,numPath;
struct Path
{
    int u,v,c;
    Path()
    {

    }
    void input()
    {
        cin>>u>>v>>c;
    }
};
vector<int> adj[N];
vector<Path> path[N];
int dep[N],up[N][20],st[N],en[N],tg=0;
void dfs(int u, int pa)
{
    up[u][0]=pa;
    st[u]=++tg;
    for (int j=1; j<20; ++j) if ((1<<j)<dep[u]) up[u][j]=up[up[u][j-1]][j-1];
    for (int v : adj[u]) if (v!=pa)
    {
//        cout<<u<<' '<<v<<'\n';
        dep[v]=dep[u]+1;
        dfs(v,u);
    }
    en[u]=++tg;
}
int findLca(int u, int v)
{
    if (dep[u]<dep[v]) swap(u,v);
    int k=dep[u]-dep[v];
    for (int i=0; i<20; ++i) if ((k>>i)&1) u=up[u][i];
    if (u==v) return u;
    for (int j=19; j>=0; --j) if ((1<<j)<dep[u])
    {
        if (up[u][j]!=up[v][j])
        {
            u=up[u][j];
            v=up[v][j];
        }
    }
    return up[u][0];
}
struct Bit
{
    ll bit[N*2];
    int n;
    void init(int _n)
    {
        n=_n;
    }
    void add(int x, ll val)
    {
        while (x<=n)
        {
            bit[x]+=val;
            x+=x&-x;
        }
    }
    ll get(int x)
    {
        ll ans=0;
        while (x>=1)
        {
            ans+=bit[x];
            x-=x&-x;
        }
        return ans;
    }
} it,nhieu;
ll NHIEU[N];
void work(int u, int pa)
{
    ll cm=0;
    for (int v : adj[u]) if (v!=pa)
    {
        work(v,u);
        cm+=it.get(st[v]);
    }
    for (Path &gogo : path[u])
    {
        ll sum=gogo.c;
        sum+=nhieu.get(st[gogo.u])+nhieu.get(st[gogo.v])+NHIEU[u];
        sum-=it.get(st[gogo.u])+it.get(st[gogo.v]);
        maximize(cm,sum);
    }
    it.add(st[u],cm); it.add(en[u]+1,-cm);
    if (pa!=-1) NHIEU[pa]+=cm;
    nhieu.add(st[u],NHIEU[u]); nhieu.add(en[u]+1,-NHIEU[u]);
}
void solve()
{
    cin>>numNode;
    for (int i=1; i<numNode; ++i)
    {
        int u,v; cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dep[1]=1;
    dfs(1,-1);
//    int u=4,v=3;
//    for (int i=1; i<=numNode; ++i) cout<<dep[i]<<' ';
//    return;
//    cout<<findLca(u,v);
//    return;
    cin>>numPath;
    for (int i=1; i<=numPath; ++i)
    {
        Path cm; cm.input();
        int lca=findLca(cm.u,cm.v);
//        cout<<lca<<'\n';
        path[lca].pb(cm);
    }
    it.init(2*numNode);
    nhieu.init(2*numNode);
    work(1,-1);
    cout<<it.get(st[1]);
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

    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