Submission #148149

#	Time	Username	Problem	Language	Result	Execution time	Memory
148149		Charis02	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	518 ms	49436 KiB

election_campaign

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 100004
#define INF 1e9+7

using namespace std;

ll n,m,x,y,a[N],b[N],c[N],depth[N],dp[N][25],tin[N],tout[N],countt,ans[N];
ll pedia[N],seg[4*N],lazy[4*N];
vector < vector < ll > > graph(N);
vector < vector < ll > > queries(N);

void init(ll cur,ll par)
{
    dp[cur][0] = par;
    depth[cur] = depth[par] + 1;
    tin[cur] = countt++;

    rep(i,0,graph[cur].size())
    {
        if(graph[cur][i] == par)
            continue;

        init(graph[cur][i],cur);
    }

    tout[cur] = countt++;

    return;
}

ll jump(ll cur,ll i)
{
    if(dp[cur][i])
        return dp[cur][i];

    return dp[cur][i] = jump(jump(cur,i-1),i-1);
}

bool isancestor(ll i,ll j)
{
    return (tin[i] <= tin[j] && tout[i] >= tout[j]);
}

ll lca(ll i,ll j)
{
    if(isancestor(i,j))
        return i;

    if(isancestor(j,i))
        return j;

    for(int p = 19;p >= 0;p--)
    {
        if(!isancestor(jump(i,p),j))
        {
            i = jump(i,p);
        }
    }

    return jump(i,0);
}

void relax(ll low,ll high,ll pos)
{
    if(lazy[pos])
    {
        seg[pos] += lazy[pos];

        if(low != high)
        {
            lazy[pos*2+1] += lazy[pos];
            lazy[pos*2+2] += lazy[pos];
        }

        lazy[pos] = 0;
    }

    return;
}

void update(ll low,ll high,ll pos,ll slow,ll shigh,ll val)
{
    relax(low,high,pos);

    if(low >= slow && high <= shigh)
    {
        seg[pos] += val;

        if(low != high)
        {
            lazy[pos*2+1] += val;
            lazy[pos*2+2] += val;
        }

        return;
    }
    if(low > shigh || high < slow)
        return;

    ll mid = (low+high)/2;

    update(low,mid,pos*2+1,slow,shigh,val);
    update(mid+1,high,pos*2+2,slow,shigh,val);

    seg[pos] = seg[pos*2+1]+seg[pos*2+2];
    return;
}

ll query(ll low,ll high,ll pos,ll slow)
{
    relax(low,high,pos);

    if(low == high && low == slow)
    {
        return seg[pos];
    }
    if(low > slow || high < slow)
        return 0;

    ll mid = (low+high)/2;

    return query(low,mid,pos*2+1,slow)+query(mid+1,high,pos*2+2,slow);
}

ll solve(ll cur,ll par)
{
    if(ans[cur] != -1)
        return ans[cur];

    ll res = 0;

    rep(i,0,graph[cur].size())
    {
        if(graph[cur][i] == par)
            continue;

        pedia[cur] += solve(graph[cur][i],cur);
    }

    rep(i,0,graph[cur].size())
    {
        if(graph[cur][i] == par)
            continue;

        ll v = graph[cur][i];
        update(0,countt,0,tin[v],tout[v],pedia[cur] - ans[v]);
    }

    res = pedia[cur];

    rep(i,0,queries[cur].size())
    {
        ll j = queries[cur][i];
        ll cand = -pedia[cur] + pedia[a[j]] + pedia[b[j]] + c[j];

        cand += query(0,countt,0,tin[a[j]]);
        cand += query(0,countt,0,tin[b[j]]);

        //cout << cur << " " << j << " " << pedia[cur] << " "<< c[j] << " "<<query(0,countt,0,tin[a[j]]) << " " << ans[a[j]] << " "<<cand << "\n";

        res = max(res,cand);
    }

    //cout << cur << " " << res << "\n";

    return ans[cur] = res;
}

int main()
{
   // ios_base::sync_with_stdio(false);

    cin >> n;

    rep(i,0,n-1)
    {
        cin >> x >> y;

        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    init(1,1);

    cin >> m;

    rep(i,0,m)
    {
        cin >> a[i] >> b[i] >> c[i];

        queries[lca(a[i],b[i])].push_back(i);
    }

    memset(ans,-1,sizeof ans);

    cout << solve(1,1) << endl;

    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'void init(long long int, long long int)':
election_campaign.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
election_campaign.cpp:30:9:
     rep(i,0,graph[cur].size())
         ~~~~~~~~~~~~~~~~~~~~~       
election_campaign.cpp:30:5: note: in expansion of macro 'rep'
     rep(i,0,graph[cur].size())
     ^~~
election_campaign.cpp: In function 'long long int solve(long long int, long long int)':
election_campaign.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
election_campaign.cpp:144:9:
     rep(i,0,graph[cur].size())
         ~~~~~~~~~~~~~~~~~~~~~       
election_campaign.cpp:144:5: note: in expansion of macro 'rep'
     rep(i,0,graph[cur].size())
     ^~~
election_campaign.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
election_campaign.cpp:152:9:
     rep(i,0,graph[cur].size())
         ~~~~~~~~~~~~~~~~~~~~~       
election_campaign.cpp:152:5: note: in expansion of macro 'rep'
     rep(i,0,graph[cur].size())
     ^~~
election_campaign.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
election_campaign.cpp:163:9:
     rep(i,0,queries[cur].size())
         ~~~~~~~~~~~~~~~~~~~~~~~     
election_campaign.cpp:163:5: note: in expansion of macro 'rep'
     rep(i,0,queries[cur].size())
     ^~~

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