oj.uz

Submission #148149

# Submission time Handle Problem Language Result Execution time Memory
148149 2019-08-31T14:58:56 Z Charis02 Election Campaign (JOI15_election_campaign) C++14
10 / 100
 518 ms 49436 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][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

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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5884 KB Output is correct
2 Correct 7 ms 5908 KB Output is correct
3 Correct 7 ms 5880 KB Output is correct
4 Correct 9 ms 6264 KB Output is correct
5 Incorrect 263 ms 39864 KB Output isn't correct
6 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 9 ms 6264 KB Output is correct
4 Correct 417 ms 49084 KB Output is correct
5 Correct 423 ms 48984 KB Output is correct
6 Correct 428 ms 48972 KB Output is correct
7 Correct 417 ms 49104 KB Output is correct
8 Correct 422 ms 49144 KB Output is correct
9 Correct 420 ms 48988 KB Output is correct
10 Correct 436 ms 49016 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 9 ms 6264 KB Output is correct
4 Correct 417 ms 49084 KB Output is correct
5 Correct 423 ms 48984 KB Output is correct
6 Correct 428 ms 48972 KB Output is correct
7 Correct 417 ms 49104 KB Output is correct
8 Correct 422 ms 49144 KB Output is correct
9 Correct 420 ms 48988 KB Output is correct
10 Correct 436 ms 49016 KB Output is correct
11 Correct 45 ms 7416 KB Output is correct
12 Correct 443 ms 49264 KB Output is correct
13 Correct 443 ms 49400 KB Output is correct
14 Correct 438 ms 49436 KB Output is correct
15 Correct 443 ms 49292 KB Output is correct
16 Correct 437 ms 49344 KB Output is correct
17 Correct 444 ms 49416 KB Output is correct
18 Correct 463 ms 49316 KB Output is correct
19 Correct 437 ms 49364 KB Output is correct
20 Correct 437 ms 49404 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 518 ms 42208 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 5884 KB Output is correct
2 Correct 7 ms 5908 KB Output is correct
3 Correct 7 ms 5880 KB Output is correct
4 Correct 9 ms 6264 KB Output is correct
5 Incorrect 263 ms 39864 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5884 KB Output is correct
2 Correct 7 ms 5908 KB Output is correct
3 Correct 7 ms 5880 KB Output is correct
4 Correct 9 ms 6264 KB Output is correct
5 Incorrect 263 ms 39864 KB Output isn't correct
6 Halted 0 ms 0 KB -