Submission #468580

#	Time	Username	Problem	Language	Result	Execution time	Memory
468580		stefantaga	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	268 ms	47120 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;
int nr[200005],niv[200005],tatic[200005],q,q2,prim[200005],mar[200005],max_fiu[200005],cnt[200005],primul[200005],id[200005],poz[200005];
vector <int> v[200005];
int rmq[200005][20];
void dfs(int x,int tata,int nivel)
{
    nr[++q2]=x;
    niv[x]=nivel;
    mar[x]=1;
    tatic[x]=tata;
    if (prim[x]==0)
    {
        prim[x]=q2;
    }
    for (int i=0;i<v[x].size();i++)
    {
        int nod=v[x][i];
        if (tata!=nod)
        {
            dfs(nod,x,nivel+1);
            mar[x]+=mar[nod];
            if (mar[nod]>mar[max_fiu[x]])
            {
                max_fiu[x]=nod;
            }
            nr[++q2]=x;
        }
    }
}
void split (int x,int t)
{
    cnt[q]++;
    if (cnt[q]==1)
    {
        primul[q]=x;
    }
    id[x]=q;
    poz[x]=cnt[q];
    if (mar[x]==1)
    {
        return;
    }
    split(max_fiu[x],x);
    for (int i=0;i<v[x].size();i++)
    {
        int nod=v[x][i];
        if (nod!=t&&nod!=max_fiu[x])
        {
            q++;
            split(nod,x);
        }
    }
}

int lca(int x,int y)
{
    if (x==y)
    {
        return x;
    }
    x=prim[x];
    y=prim[y];
    if (x>y)
    {
        swap(x,y);
    }
    int lg=log2(y-x);
    if (niv[rmq[x][lg]]<niv[rmq[y-(1<<lg)+1][lg]])
    {
        return rmq[x][lg];
    }
    else
    {
        return rmq[y-(1<<lg)+1][lg];
    }
}
struct wow
{
    int x,y,z;
};
vector <wow> sal[200005];
int din[200005],sumafii[200005];
class SegmentTree
{
    int *arb;
public:
    inline void Initialize(int Elems)
    {
        arb = new int [((Elems<<4)+1)];
        for (int i=1;i<=(Elems<<2);i++)
        {
            arb[i]=0;
        }
        return;
    }
    inline void update(int st,int dr,int nod,int poz,int val)
    {
        if (st==dr)
        {
            arb[nod]=val;
            return;
        }
        int mij=(st+dr)/2;
        if (poz<=mij)
        {
            update(st,mij,2*nod,poz,val);
        }
        else
        {
            update(mij+1,dr,2*nod+1,poz,val);
        }
        arb[nod]=arb[2*nod+1]+arb[2*nod];
    }
    inline int query(int st,int dr,int nod,int ua,int ub)
    {
        if (ua<=st&&dr<=ub)
        {
            return arb[nod];
        }
        int mij=(st+dr)/2;
        int sum=0;
        if (ua<=mij)
        {
            sum=sum+query(st,mij,2*nod,ua,ub);
        }
        if (mij<ub)
        {
            sum=sum+query(mij+1,dr,2*nod+1,ua,ub);
        }
        return sum;
    }
}*chains;
int query(int x,int y)
{
    if (id[x]==id[y])
    {
        int st,dr;
        st=poz[x];
        dr=poz[y];
        if (st>dr)
        {
            swap(st,dr);
        }
        return chains[id[x]].query(1,cnt[id[x]],1,st,dr);
    }
    if (niv[primul[id[x]]]>niv[primul[id[y]]])
    {
        swap(x,y);
    }
    return query(y,primul[id[y]])+query(tatic[primul[id[y]]],x);
}
void solve(int x,int tata)
{
    int i;
    for (i=0;i<v[x].size();i++)
    {
        if (v[x][i]!=tata)
        {
            solve(v[x][i],x);
        }
    }
    for (i=0;i<v[x].size();i++)
    {
        if (v[x][i]!=tata)
        {
            sumafii[x]+=din[v[x][i]];
        }
    }
    din[x]=sumafii[x];
    for (i=0;i<sal[x].size();i++)
    {
        int suma=sumafii[x]+query(x,sal[x][i].x)+query(x,sal[x][i].y);
        din[x]=max(din[x],suma+sal[x][i].z);
    }
    chains[id[x]].update(1,cnt[id[x]],1,poz[x],sumafii[x]-din[x]);
}
int n,i,x,y,lg,p,j,m,z;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n;
    for (i=1;i<n;i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0,1);
    q=1;
    split(1,0);
    chains = new SegmentTree[(q+1)];
    for (i=1;i<=q;i++)
    {
        chains[i].Initialize(cnt[i]);
    }
    for (i=1;i<=q2;i++)
    {
        rmq[i][0]=nr[i];
    }
    lg=log2(q2);
    p=1;
    for (i=1;i<=lg;i++)
    {
        for (j=1;j<=q2-p+1;j++)
        {
            if (niv[rmq[j][i-1]]<niv[rmq[j+p][i-1]])
            {
                rmq[j][i]=rmq[j][i-1];
            }
            else
            {
                rmq[j][i]=rmq[j+p][i-1];
            }
        }
        p=p*2;
    }
    cin>>m;
    for (i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        sal[lca(x,y)].push_back(wow{x,y,z});
    }
    solve(1,0);
    cout<<din[1];
    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs(int, int, int)':
election_campaign.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i=0;i<v[x].size();i++)
      |                  ~^~~~~~~~~~~~
election_campaign.cpp: In function 'void split(int, int)':
election_campaign.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i=0;i<v[x].size();i++)
      |                  ~^~~~~~~~~~~~
election_campaign.cpp: In function 'void solve(int, int)':
election_campaign.cpp:157:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for (i=0;i<v[x].size();i++)
      |              ~^~~~~~~~~~~~
election_campaign.cpp:164:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for (i=0;i<v[x].size();i++)
      |              ~^~~~~~~~~~~~
election_campaign.cpp:172:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<wow>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |     for (i=0;i<sal[x].size();i++)
      |              ~^~~~~~~~~~~~~~

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