Submission #298479

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
298479	2020-09-13T01:43:07 Z	XmtosX	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	554 ms	42860 KB

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

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

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

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9728 KB	Output is correct
2	Correct	6 ms	9728 KB	Output is correct
3	Correct	8 ms	9984 KB	Output is correct
4	Correct	422 ms	42352 KB	Output is correct
5	Correct	424 ms	42352 KB	Output is correct
6	Correct	379 ms	42352 KB	Output is correct
7	Correct	413 ms	42476 KB	Output is correct
8	Correct	413 ms	42352 KB	Output is correct
9	Correct	377 ms	42352 KB	Output is correct
10	Correct	416 ms	42352 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9728 KB	Output is correct
2	Correct	6 ms	9728 KB	Output is correct
3	Correct	8 ms	9984 KB	Output is correct
4	Correct	422 ms	42352 KB	Output is correct
5	Correct	424 ms	42352 KB	Output is correct
6	Correct	379 ms	42352 KB	Output is correct
7	Correct	413 ms	42476 KB	Output is correct
8	Correct	413 ms	42352 KB	Output is correct
9	Correct	377 ms	42352 KB	Output is correct
10	Correct	416 ms	42352 KB	Output is correct
11	Correct	46 ms	11000 KB	Output is correct
12	Correct	430 ms	42604 KB	Output is correct
13	Correct	435 ms	42860 KB	Output is correct
14	Correct	390 ms	42608 KB	Output is correct
15	Correct	425 ms	42608 KB	Output is correct
16	Correct	398 ms	42608 KB	Output is correct
17	Correct	435 ms	42856 KB	Output is correct
18	Correct	425 ms	42600 KB	Output is correct
19	Correct	390 ms	42652 KB	Output is correct
20	Correct	435 ms	42704 KB	Output is correct