Submission #298488

#	Time	Username	Problem	Language	Result	Execution time	Memory
298488		XmtosX	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	709 ms	52556 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 <long long> v[N],pfx[N][2];
vector <pair<long long,long long> > 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,long long> 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,int idx)
{
    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][idx][idx2];
    idx1--;
    if (idx1>=0)
        ans-=pfx[x][idx][idx1];
    if (chn[x].back().first>r)
    {
        l=chn[x].back().first-1;
        ans+= query(findpar(sprs[x][0]),idx);
    }
    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];
        int A= V[x][i].a;
        int 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;
            int L=l,R=r;
            cur+= query(findpar(V[x][i].a),0);
            l=L,r=R;
            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;
            int L=l,R=r;
            cur+= query(findpar(V[x][i].b),0);
            l=L,r=R;
            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;
    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][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<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<long long 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:86:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i=0;i<v[x].size();i++)
      |                  ~^~~~~~~~~~~~
election_campaign.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i=0;i<V[x].size();i++)
      |                  ~^~~~~~~~~~~~
election_campaign.cpp:140:9: warning: variable 'o' set but not used [-Wunused-but-set-variable]
  140 |     int o;
      |         ^
election_campaign.cpp: In function 'int query(int, 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: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40