Submission #298479

#	Time	Username	Problem	Language	Result	Execution time	Memory
298479		XmtosX	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	554 ms	42860 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+3;
int n,q,sprs[N][20],lvl[N],dpsons[N],dp[N],par[N],sz[N],l,r;
vector <int> v[N],pfx[N];
vector <pair<int,int> > chn[N];
bool yes,yes1;
struct node
{
    int a,b,upa,upb,ans;
};
vector <node> V[N];
int findpar(int x)
{
    if (x==par[x])
        return x;
    return par[x]=findpar(par[x]);
}
void unun (int n1,int n2)
{
    int x1=findpar(n1);
    int x2=findpar(n2);
    par[x2]=x1;
}
void dfs1 (int x,int p)
{
    sz[x]=1;
    par[x]=x;
    sprs[x][0]=p;
    lvl[x]=lvl[p]+1;
    pair<int,int> big={0,0};
    for (int i=1;i<20;i++)
        sprs[x][i]=sprs[sprs[x][i-1]][i-1];
    for (int 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);
}
int query (int x)
{
    if (chn[x].empty())
        return 0;
    int ans=0;
    int 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][idx2];
    idx1--;
    if (idx1>=0)
        ans-=pfx[x][idx1];
    if (chn[x].back().first>r)
    {
        ans+= query(findpar(sprs[x][0]));
        ans-= dp[x];
    }
    return ans;
}
void dfs (int x,int p)
{
    for (int 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];
    int maxx=dpsons[x];
    for (int i=0;i<V[x].size();i++)
    {
        int 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];
        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= max(lvl[V[x][i].upa],lvl[x]+1);
            cur+= query(findpar(V[x][i].a));
        }
        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= max(lvl[V[x][i].upb],lvl[x]+1);
            cur+= query(findpar(V[x][i].b));
        }
        cur+= V[x][i].ans;
        maxx=max(maxx,cur);
    }
    dp[x]=maxx;
    int idx=findpar(x);
    pair<int,int> P= {lvl[x],x};
    int o;
    if (!chn[idx].empty())
        o=chn[idx].back().second;
    chn[idx].push_back(P);
    if (pfx[idx].empty())
        pfx[idx].push_back(dpsons[x]);
    else
    {
        pfx[idx].push_back(pfx[idx].back());
        pfx[idx].back()+= dpsons[x]-dp[o];
    }
}
pair<int,int> lca(int x,int y)
{
    pair<int,int> p;
    if (lvl[x]<lvl[y])
        swap(x,y);
    for (int 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 (int 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()
{
    int maxx=0;
    cin >>n;
    for (int i=0;i<n-1;i++)
    {
        int a,b;
        cin >>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int st=1;
    dfs1(st,0);
    cin >>q;
    while(q--)
    {
        int x,y,z;
        cin >>x>>y>>z;
        pair<int,int> p=lca(x,y);
        int lc= sprs[p.first][0];
        int 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 (stderr)

election_campaign.cpp: In function 'void dfs1(int, int)':
election_campaign.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i=0;i<v[x].size();i++)
      |                  ~^~~~~~~~~~~~
election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:88:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i=0;i<v[x].size();i++)
      |                  ~^~~~~~~~~~~~
election_campaign.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (int i=0;i<V[x].size();i++)
      |                  ~^~~~~~~~~~~~
election_campaign.cpp: In function 'int query(int)':
election_campaign.cpp:76:9: warning: 'idx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |     idx1--;
      |     ~~~~^~
election_campaign.cpp:75:20: warning: 'idx2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |     ans=pfx[x][idx2];
      |                    ^
election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:135:41: warning: 'o' may be used uninitialized in this function [-Wmaybe-uninitialized]
  135 |         pfx[idx].back()+= dpsons[x]-dp[o];
      |                                     ~~~~^

• Subtask 1: 0 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40