Submission #234274

#	Time	Username	Problem	Language	Result	Execution time	Memory
234274		Andrei_Cotor	Duathlon (APIO18_duathlon)	C++11	23 / 100	125 ms	31356 KiB

count_triplets

/*
      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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10