oj.uz

Submission #298486

# Submission time Handle Problem Language Result Execution time Memory
298486 2020-09-13T02:12:09 Z XmtosX Election Campaign (JOI15_election_campaign) C++17
10 / 100
 634 ms 59152 KB 
#include <bits/stdc++.h>
using namespace std;
const long long N=1e5+3;
long long n,q,sprs[N][20],lvl[N],dpsons[N],dp[N],par[N],sz[N],l,r;
vector <long long> v[N],pfx[N][2];
vector <pair<long long,long long> > chn[N];
bool yes,yes1;
struct node
{
    long long a,b,upa,upb,ans;
};
vector <node> V[N];
long long findpar(long long x)
{
    if (x==par[x])
        return x;
    return par[x]=findpar(par[x]);
}
void unun (long long n1,long long n2)
{
    long long x1=findpar(n1);
    long long x2=findpar(n2);
    par[x2]=x1;
}
void dfs1 (long long x,long long p)
{
    sz[x]=1;
    par[x]=x;
    sprs[x][0]=p;
    lvl[x]=lvl[p]+1;
    pair<long long,long long> big={0,0};
    for (long long i=1;i<20;i++)
        sprs[x][i]=sprs[sprs[x][i-1]][i-1];
    for (long long i=0;i<v[x].size();i++)
    {
        if (v[x][i]!=p)
        {
            dfs1(v[x][i],x);
            sz[x]+=sz[v[x][i]];
            big=max(big,make_pair(sz[v[x][i]],v[x][i]));
        }
    }
    if (big.first)
        unun(x,big.second);
}
long long query (long long x,long long idx)
{
    long long ans=0;
    long long low=0,high=chn[x].size()-1,mid,idx1,idx2;
    while (low<=high)
    {
        mid= (low+high)/2;
        if (chn[x][mid].first>l)
            low=mid+1;
        else
        {
            idx1=mid;
            high=mid-1;
        }
    }
    low=0,high=chn[x].size()-1;
    while (low<=high)
    {
        mid= (low+high)/2;
        if (chn[x][mid].first<r)
            high=mid-1;
        else
        {
            idx2=mid;
            low=mid+1;
        }
    }
    ans=pfx[x][idx][idx2];
    idx1--;
    if (idx1>=0)
        ans-=pfx[x][idx][idx1];
    if (chn[x].back().first>r)
    {
        ans+= query(findpar(sprs[x][0]),idx);
    }
    return ans;
}
void dfs (long long x,long long p)
{
    for (long long i=0;i<v[x].size();i++)
    {
        if (v[x][i]!=p)
        {
            dfs(v[x][i],x);
            dpsons[x]+=dp[v[x][i]];
        }
    }

    dp[x]=dpsons[x];
    long long maxx=dpsons[x];
    for (long long i=0;i<V[x].size();i++)
    {
        long long cur=dpsons[x];
        cur-= dp[V[x][i].upa];
        cur-= dp[V[x][i].upb];
        cur+= dpsons[V[x][i].a];
        cur+= dpsons[V[x][i].b];
        long long A= V[x][i].a;
        long long B= V[x][i].b;
        if (x!=V[x][i].a&&sprs[V[x][i].a][0]!=x)
        {
            V[x][i].a=sprs[V[x][i].a][0];
            l= lvl[V[x][i].a];
            r= lvl[x]+1;
            cur+= query(findpar(V[x][i].a),0);
            r++;
            cur-= dp[A];
            if (l>=r)
                cur-= (query(findpar(V[x][i].a),1));
        }
        if (x!=V[x][i].b&&sprs[V[x][i].b][0]!=x)
        {
            V[x][i].b=sprs[V[x][i].b][0];
            l= lvl[V[x][i].b];
            r= lvl[x]+1;
            cur+= query(findpar(V[x][i].b),0);
            r++;
            cur-= dp[B];
            if (l>=r)
            {
                cur-= (query(findpar(V[x][i].b),1));
            }
        }
        cur+= V[x][i].ans;
        maxx=max(maxx,cur);
    }
    dp[x]=maxx;
    long long idx=findpar(x);
    pair<long long,long long> P= {lvl[x],x};
    long long o;
    if (!chn[idx].empty())
        o=chn[idx].back().second;
    chn[idx].push_back(P);
    if (pfx[idx][0].empty())
    {
        pfx[idx][0].push_back(dpsons[x]);
        pfx[idx][1].push_back(dp[x]);
    }
    else
    {
        pfx[idx][0].push_back(pfx[idx][0].back());
        pfx[idx][0].back()+= dpsons[x];
        pfx[idx][1].push_back(pfx[idx][1].back());
        pfx[idx][1].back()+= dp[x];
    }
}
pair<long long,long long> lca(long long x,long long y)
{
    pair<long long,long long> p;
    if (lvl[x]<lvl[y])
        swap(x,y);
    for (long long i=19;i>=0;i--)
    {
        if (lvl[sprs[x][i]]>lvl[y])
            x=sprs[x][i];
    }
    if (sprs[x][0]==y)
    {
        p={x,y};
        return p;
    }
    if (lvl[x]!=lvl[y])
        x=sprs[x][0];
    for (long long i=19;i>=0;i--)
    {
        if (sprs[x][i]!=sprs[y][i])
        {
            x=sprs[x][i];
            y=sprs[y][i];
        }
    }
    p={x,y};
    return p;
}
int main()
{
    long long maxx=0;
    cin >>n;
    for (long long i=0;i<n-1;i++)
    {
        long long a,b;
        cin >>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    long long st=1;
    dfs1(st,0);
    cin >>q;
    while(q--)
    {
        long long x,y,z;
        cin >>x>>y>>z;
        pair<long long,long long> p=lca(x,y);
        long long lc= sprs[p.first][0];
        long long val=z;
        node A= {x,y,p.first,p.second,val};
        maxx=max(maxx,z);
        V[lc].push_back(A);
    }
    dfs(st,0);
    cout <<dp[st];
    return 0;
}
/*
7
3 4
6 5
2 7
1 5
7 5
4 5
5
4 3 10
5 6 5
2 6 9
7 2 2
1 3 8

8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
5
7 5 4
5 8 9
4 3 9
1 3 3
2 8 11

20
17 10
11 4
8 3
3 16
1 14
15 18
5 4
6 18
10 18
19 4
16 7
2 13
4 12
12 20
9 20
18 13
20 14
14 7
13 7
15
19 9 2341
13 8 6974
8 3 3339
15 17 6515
10 13 4370
1 7 8376
18 2 9272
6 7 4595
1 20 505
10 9 308
6 19 8937
2 15 5072
5 4 4217
2 4 4170
19 12 8204
*/

Compilation message

election_campaign.cpp: In function 'void dfs1(long long int, long long int)':
election_campaign.cpp:34:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (long long i=0;i<v[x].size();i++)
      |                        ~^~~~~~~~~~~~
election_campaign.cpp: In function 'void dfs(long long int, long long int)':
election_campaign.cpp:85:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (long long i=0;i<v[x].size();i++)
      |                        ~^~~~~~~~~~~~
election_campaign.cpp:96:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (long long i=0;i<V[x].size();i++)
      |                        ~^~~~~~~~~~~~
election_campaign.cpp:135:15: warning: variable 'o' set but not used [-Wunused-but-set-variable]
  135 |     long long o;
      |               ^
election_campaign.cpp: In function 'long long int query(long long int, long long int)':
election_campaign.cpp:74:9: warning: 'idx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |     idx1--;
      |     ~~~~^~
election_campaign.cpp:73:25: warning: 'idx2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |     ans=pfx[x][idx][idx2];
      |                         ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12032 KB Output is correct
2 Correct 8 ms 12032 KB Output is correct
3 Correct 8 ms 12032 KB Output is correct
4 Correct 9 ms 12416 KB Output is correct
5 Incorrect 260 ms 41920 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 8 ms 12032 KB Output is correct
2 Correct 8 ms 12032 KB Output is correct
3 Correct 10 ms 12544 KB Output is correct
4 Correct 476 ms 58600 KB Output is correct
5 Correct 470 ms 59012 KB Output is correct
6 Correct 410 ms 58728 KB Output is correct
7 Correct 475 ms 58728 KB Output is correct
8 Correct 482 ms 59060 KB Output is correct
9 Correct 417 ms 59152 KB Output is correct
10 Correct 487 ms 58604 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12032 KB Output is correct
2 Correct 8 ms 12032 KB Output is correct
3 Correct 10 ms 12544 KB Output is correct
4 Correct 476 ms 58600 KB Output is correct
5 Correct 470 ms 59012 KB Output is correct
6 Correct 410 ms 58728 KB Output is correct
7 Correct 475 ms 58728 KB Output is correct
8 Correct 482 ms 59060 KB Output is correct
9 Correct 417 ms 59152 KB Output is correct
10 Correct 487 ms 58604 KB Output is correct
11 Correct 52 ms 13944 KB Output is correct
12 Correct 494 ms 58632 KB Output is correct
13 Correct 488 ms 58600 KB Output is correct
14 Correct 430 ms 58980 KB Output is correct
15 Correct 496 ms 58980 KB Output is correct
16 Correct 432 ms 58600 KB Output is correct
17 Correct 493 ms 58600 KB Output is correct
18 Correct 497 ms 58580 KB Output is correct
19 Correct 433 ms 59108 KB Output is correct
20 Correct 506 ms 58980 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12032 KB Output is correct
2 Correct 8 ms 12032 KB Output is correct
3 Correct 8 ms 12032 KB Output is correct
4 Correct 9 ms 12416 KB Output is correct
5 Incorrect 260 ms 41920 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12032 KB Output is correct
2 Correct 8 ms 12032 KB Output is correct
3 Correct 8 ms 12032 KB Output is correct
4 Correct 9 ms 12416 KB Output is correct
5 Incorrect 260 ms 41920 KB Output isn't correct
6 Halted 0 ms 0 KB -