oj.uz

Submission #468567

# Submission time Handle Problem Language Result Execution time Memory
468567 2021-08-28T18:57:09 Z stefantaga Election Campaign (JOI15_election_campaign) C++14
20 / 100
 1000 ms 41940 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 6 ms 9932 KB Output is correct
5 Correct 102 ms 32468 KB Output is correct
6 Correct 91 ms 38628 KB Output is correct
7 Correct 98 ms 36420 KB Output is correct
8 Correct 96 ms 32540 KB Output is correct
9 Correct 99 ms 35236 KB Output is correct
10 Correct 92 ms 32544 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 7 ms 9932 KB Output is correct
4 Execution timed out 1078 ms 41884 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 7 ms 9932 KB Output is correct
4 Execution timed out 1078 ms 41884 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 35316 KB Output is correct
2 Execution timed out 1083 ms 41940 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 6 ms 9932 KB Output is correct
5 Correct 102 ms 32468 KB Output is correct
6 Correct 91 ms 38628 KB Output is correct
7 Correct 98 ms 36420 KB Output is correct
8 Correct 96 ms 32540 KB Output is correct
9 Correct 99 ms 35236 KB Output is correct
10 Correct 92 ms 32544 KB Output is correct
11 Correct 6 ms 9932 KB Output is correct
12 Correct 7 ms 9992 KB Output is correct
13 Correct 9 ms 9988 KB Output is correct
14 Correct 6 ms 9920 KB Output is correct
15 Correct 9 ms 9968 KB Output is correct
16 Correct 8 ms 9992 KB Output is correct
17 Correct 6 ms 9988 KB Output is correct
18 Correct 7 ms 9924 KB Output is correct
19 Correct 6 ms 9992 KB Output is correct
20 Correct 8 ms 10048 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 6 ms 9932 KB Output is correct
5 Correct 102 ms 32468 KB Output is correct
6 Correct 91 ms 38628 KB Output is correct
7 Correct 98 ms 36420 KB Output is correct
8 Correct 96 ms 32540 KB Output is correct
9 Correct 99 ms 35236 KB Output is correct
10 Correct 92 ms 32544 KB Output is correct
11 Correct 7 ms 9676 KB Output is correct
12 Correct 7 ms 9676 KB Output is correct
13 Correct 7 ms 9932 KB Output is correct
14 Execution timed out 1078 ms 41884 KB Time limit exceeded
15 Halted 0 ms 0 KB -