Submission #147947

#	Time	Username	Problem	Language	Result	Execution time	Memory
147947		Charis02	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	376 ms	41544 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][20],tin[N],tout[N],countt,ans[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);
}

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;

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

   // cout<<"without " << cur << " "<< res<<endl;

    rep(i,0,queries[cur].size())
    {
        ll q = queries[cur][i];

        ll candidate = c[q];

            rep(j,0,graph[cur].size())
            {
                if(graph[cur][j] == par||isancestor(graph[cur][j],a[q])||isancestor(graph[cur][j],b[q]))
                    continue;

                candidate += solve(graph[cur][j],cur);
        }

if(a[q]!=cur)
        rep(j,0,graph[a[q]].size())
        {
            if(!isancestor(a[q],graph[a[q]][j]))
                continue;

            candidate += solve(graph[a[q]][j],a[q]);
        }
if(b[q]!=cur)
        rep(j,0,graph[b[q]].size())
        {
            if(!isancestor(b[q],graph[b[q]][j]))
                continue;

            candidate += solve(graph[b[q]][j],b[q]);
        }

        //cout << cur << " " << candidate << " "<< a[q] << " "<<b[q]<< " "<<c[q]<<endl;
        res = max(res,candidate);
    }

   // cout<<cur<<" "<<res<<endl;
    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:29:9:
     rep(i,0,graph[cur].size())
         ~~~~~~~~~~~~~~~~~~~~~       
election_campaign.cpp:29: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:81:9:
     rep(i,0,graph[cur].size())
         ~~~~~~~~~~~~~~~~~~~~~       
election_campaign.cpp:81: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:91:9:
     rep(i,0,queries[cur].size())
         ~~~~~~~~~~~~~~~~~~~~~~~     
election_campaign.cpp:91:5: note: in expansion of macro 'rep'
     rep(i,0,queries[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:97:17:
             rep(j,0,graph[cur].size())
                 ~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:97:13: note: in expansion of macro 'rep'
             rep(j,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:106:13:
         rep(j,0,graph[a[q]].size())
             ~~~~~~~~~~~~~~~~~~~~~~  
election_campaign.cpp:106:9: note: in expansion of macro 'rep'
         rep(j,0,graph[a[q]].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:114:13:
         rep(j,0,graph[b[q]].size())
             ~~~~~~~~~~~~~~~~~~~~~~  
election_campaign.cpp:114:9: note: in expansion of macro 'rep'
         rep(j,0,graph[b[q]].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