Submission #147947

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
147947	2019-08-31T09:28:43 Z	Charis02	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	376 ms	41544 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5880 KB	Output is correct
2	Correct	7 ms	5880 KB	Output is correct
3	Incorrect	7 ms	5880 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5880 KB	Output is correct
2	Correct	7 ms	5880 KB	Output is correct
3	Correct	8 ms	6136 KB	Output is correct
4	Correct	298 ms	41144 KB	Output is correct
5	Correct	291 ms	41208 KB	Output is correct
6	Correct	293 ms	41264 KB	Output is correct
7	Correct	312 ms	41128 KB	Output is correct
8	Correct	318 ms	41180 KB	Output is correct
9	Correct	319 ms	41440 KB	Output is correct
10	Correct	315 ms	41248 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5880 KB	Output is correct
2	Correct	7 ms	5880 KB	Output is correct
3	Correct	8 ms	6136 KB	Output is correct
4	Correct	298 ms	41144 KB	Output is correct
5	Correct	291 ms	41208 KB	Output is correct
6	Correct	293 ms	41264 KB	Output is correct
7	Correct	312 ms	41128 KB	Output is correct
8	Correct	318 ms	41180 KB	Output is correct
9	Correct	319 ms	41440 KB	Output is correct
10	Correct	315 ms	41248 KB	Output is correct
11	Correct	38 ms	7288 KB	Output is correct
12	Correct	328 ms	41544 KB	Output is correct
13	Correct	324 ms	41528 KB	Output is correct
14	Correct	312 ms	41424 KB	Output is correct
15	Correct	315 ms	41460 KB	Output is correct
16	Correct	308 ms	41464 KB	Output is correct
17	Correct	325 ms	41456 KB	Output is correct
18	Correct	309 ms	41464 KB	Output is correct
19	Correct	308 ms	41464 KB	Output is correct
20	Correct	317 ms	41528 KB	Output is correct