oj.uz

Submission #234274

# Submission time Handle Problem Language Result Execution time Memory
234274 2020-05-23T17:02:28 Z Andrei_Cotor Duathlon (APIO18_duathlon) C++11
23 / 100
 125 ms 31356 KB 
/*
      F
S   |-|        |-|
|   |          | C
C   | O--S     | |
|   | |        | O--S
F   | C        |
    |-|        |-|
                 F
*/

//desen 2: se foloseste o muchie de intoarcere care porneste din nod. Nodul c se va afla deasupra lui nod, s va fi legat de el, iar la f se va ajunge prin muchia de intoarcere

#include<iostream>
#include<vector>

using namespace std;

long long Vals1[100005];
int Vals2[100005];
long long F1[100005],F2[100005];

void update(int poz, long long val1, int val2)
{
    while(poz<=100000)
    {
        F1[poz]+=val1;
        F2[poz]+=1LL*val2;
        poz=poz+(poz&(poz^(poz-1)));
    }
}

void add(int val, int lev)
{
    long long delta1=1LL*val*lev-Vals1[lev];
    int delta2=val-Vals2[lev];

    update(lev,delta1,delta2);

    Vals1[lev]=1LL*val*lev;
    Vals2[lev]=val;
}

pair<long long,int> query(int poz)
{
    pair<long long,int> rez;
    rez={0,0};
    while(poz>=1)
    {
        rez.first+=F1[poz];
        rez.second+=F2[poz];

        poz=poz-(poz&(poz^(poz-1)));
    }
    return rez;
}

long long getPosib(int st, int dr, int lev) //lev e nivelul punctului in care porneste muchia de intoarcere, ultimul punct in care pot pune C
{
    if(st>dr)
        return 0;

    pair<long long,int> sum=query(dr);
    pair<long long,int> aux=query(st-1);
    sum.first-=aux.first;
    sum.second-=aux.second;

    long long rez=sum.first-1LL*lev*sum.second;
    if(rez<0) //desen 2
        rez=-rez;

    return rez;
}

vector<int> A[100005];
vector<int> Adv[100005],Ret[100005]; //muchiile de avansare si intoarcere
int Lev[100005],Sz[100005];
int Ram[100005];

void getArb(int nod, int p)
{
    Lev[nod]=1+Lev[p];
    Sz[nod]=1;
    for(auto other:A[nod])
    {
        if(other==p)
            continue;

        if(!Lev[other])
        {
            Adv[nod].push_back(other);
            getArb(other,nod);
            Sz[nod]+=Sz[other];
        }
        else
        {
            if(Lev[nod]>Lev[other])
                Ret[nod].push_back(other);
        }
    }
}

long long rez;
bool Viz[100005];

void solve(int nod, int root)
{
    Viz[nod]=1;

    //caz desen 1
    int sz=0;
    for(auto other:Adv[nod])
    {
        rez+=(1LL*sz*Sz[other]);
        sz+=Sz[other];
    }
    rez+=(1LL*sz*(Sz[root]-Sz[nod]));

    //celelalte
    for(auto other:Ret[nod])
    {
        //desen 2
        rez+=(1LL*getPosib(Lev[other]+1,Lev[nod]-1,Lev[nod])*Ram[other]);

        //desen 3
        rez+=(1LL*getPosib(Lev[other]+1,Lev[nod]-1,Lev[other])*Sz[nod]);
    }

    for(auto other:Adv[nod])
    {
        Ram[nod]=Sz[root]-Sz[other]; //cand aleg o muchie de intoarcere care se termina in nod, din subarb lui other
        add(Sz[nod]-Sz[other],Lev[nod]); //daca nodul O (din desen) e in nod

        solve(other,root);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,m;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin>>x>>y;

        A[x].push_back(y);
        A[y].push_back(x);
    }

    for(int i=1; i<=n; i++)
    {
        if(!Lev[i])
            getArb(i,0);
    }

    for(int i=1; i<=n; i++)
    {
        if(!Viz[i])
            solve(i,i);
    }

    rez*=2LL;
    cout<<rez<<"\n";
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 31356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7552 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Correct 9 ms 7552 KB Output is correct
4 Correct 9 ms 7680 KB Output is correct
5 Correct 9 ms 7680 KB Output is correct
6 Correct 10 ms 7680 KB Output is correct
7 Correct 9 ms 7680 KB Output is correct
8 Correct 9 ms 7552 KB Output is correct
9 Correct 9 ms 7552 KB Output is correct
10 Correct 9 ms 7552 KB Output is correct
11 Correct 9 ms 7552 KB Output is correct
12 Correct 9 ms 7552 KB Output is correct
13 Correct 9 ms 7552 KB Output is correct
14 Correct 10 ms 7552 KB Output is correct
15 Correct 9 ms 7552 KB Output is correct
16 Correct 9 ms 7552 KB Output is correct
17 Correct 9 ms 7552 KB Output is correct
18 Correct 9 ms 7552 KB Output is correct
19 Correct 9 ms 7552 KB Output is correct
20 Correct 9 ms 7552 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 14992 KB Output is correct
2 Correct 98 ms 14840 KB Output is correct
3 Correct 91 ms 14932 KB Output is correct
4 Correct 82 ms 14840 KB Output is correct
5 Correct 99 ms 14840 KB Output is correct
6 Correct 115 ms 24536 KB Output is correct
7 Correct 97 ms 20984 KB Output is correct
8 Correct 108 ms 19576 KB Output is correct
9 Correct 90 ms 17912 KB Output is correct
10 Correct 96 ms 14844 KB Output is correct
11 Correct 85 ms 14840 KB Output is correct
12 Correct 90 ms 14840 KB Output is correct
13 Correct 94 ms 14840 KB Output is correct
14 Correct 76 ms 14712 KB Output is correct
15 Correct 73 ms 14456 KB Output is correct
16 Correct 53 ms 12924 KB Output is correct
17 Correct 56 ms 13680 KB Output is correct
18 Correct 54 ms 13688 KB Output is correct
19 Correct 54 ms 13804 KB Output is correct
20 Correct 56 ms 13816 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 14884 KB Output is correct
2 Correct 102 ms 15096 KB Output is correct
3 Correct 114 ms 16008 KB Output is correct
4 Incorrect 125 ms 16376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -