oj.uz

Submission #147944

# Submission time Handle Problem Language Result Execution time Memory
147944 2019-08-31T09:11:29 Z Charis02 Election Campaign (JOI15_election_campaign) C++14
0 / 100
 385 ms 33576 KB 
#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);
    }

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

        ll candidate = c[q];

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

                candidate += solve(graph[cur][j],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]);
        }

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

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

        res = max(res,candidate);
    }

    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:89:9:
     rep(i,0,queries[cur].size())
         ~~~~~~~~~~~~~~~~~~~~~~~     
election_campaign.cpp:89: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 Incorrect 7 ms 5880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 385 ms 33576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

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

Subtask #6
0 / 40.0

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