Submission #468567

#	Time	Username	Problem	Language	Result	Execution time	Memory
468567		stefantaga	Election Campaign (JOI15_election_campaign)	C++14	20 / 100	1083 ms	41940 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;
int nr[200005],niv[200005],tatic[200005],q,prim[200005];
vector <int> v[200005];
int rmq[200005][20];
void dfs(int x,int tata,int nivel)
{
    nr[++q]=x;
    niv[x]=nivel;
    tatic[x]=tata;
    if (prim[x]==0)
    {
        prim[x]=q;
    }
    for (int i=0;i<v[x].size();i++)
    {
        int nod=v[x][i];
        if (tata!=nod)
        {
            dfs(nod,x,nivel+1);
            nr[++q]=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];
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 y=sal[x][i].x;
        int suma=sumafii[x];
        while (y!=x)
        {
            suma=suma+sumafii[y]-din[y];
            y=tatic[y];
        }
        y=sal[x][i].y;
        while (y!=x)
        {
            suma=suma+sumafii[y]-din[y];
            y=tatic[y];
        }
        din[x]=max(din[x],suma+sal[x][i].z);
    }
}
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);
    for (i=1;i<=q;i++)
    {
        rmq[i][0]=nr[i];
    }
    lg=log2(q);
    p=1;
    for (i=1;i<=lg;i++)
    {
        for (j=1;j<=q-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:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i=0;i<v[x].size();i++)
      |                  ~^~~~~~~~~~~~
election_campaign.cpp: In function 'void solve(int, int)':
election_campaign.cpp:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (i=0;i<v[x].size();i++)
      |              ~^~~~~~~~~~~~
election_campaign.cpp:64:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (i=0;i<v[x].size();i++)
      |              ~^~~~~~~~~~~~
election_campaign.cpp:72:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<wow>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (i=0;i<sal[x].size();i++)
      |              ~^~~~~~~~~~~~~~

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