제출 #961053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
961053		AndreiBOTO	Duathlon (APIO18_duathlon)	C++14	100 / 100	73 ms	32160 KiB

count_triplets

#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

const int NMAX=2e5+5;

long long sarb[NMAX];
vector<int>cbc[NMAX];
vector<int>v[NMAX];
stack<int>stiva;
long long kon=0;
int tmin[NMAX];
int ti[NMAX];
int timer;
int total;
int saiz;

int n;

void dfs_biconex(int p,int tata)
{
    saiz++;
    ti[p]=++timer;
    tmin[p]=timer;
    stiva.push(p);
    for(auto i:v[p])
    {
        if(tata!=i)
        {
            if(!ti[i])
            {
                dfs_biconex(i,p);
                tmin[p]=min(tmin[p],tmin[i]);
                if(tmin[i]>=ti[p])
                {
                    total++;
                    while(stiva.top()!=i)
                    {
                        cbc[n+total].push_back(stiva.top());
                        stiva.pop();
                    }
                    cbc[n+total].push_back(stiva.top());
                    stiva.pop();
                    cbc[p].push_back(n+total);
                }
            }
            else
                tmin[p]=min(tmin[p],ti[i]);
        }
    }
}

void dfs(int p)
{
    if(p>n)
        sarb[p]=0;
    else
        sarb[p]=1;
    for(auto i:cbc[p])
    {
        dfs(i);
        sarb[p]+=sarb[i];
        if(i<=n)
            kon-=sarb[i]*(sarb[i]-1);
    }
    if(p>n)
    {
        long long s=0;
        for(auto i:cbc[p])
            s+=sarb[i]*(sarb[i]-1);
        for(auto i:cbc[p])
        {
            long long more_paths=s-sarb[i]*(sarb[i]-1);
            long long above=saiz-sarb[p];
            kon-=above*(above-1);
            kon-=more_paths;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int m,i,j;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1;i<=n;i++)
    {
        if(!ti[i])
        {
            saiz=0;
            dfs_biconex(i,0);
            kon+=1LL*saiz*(saiz-1)*(saiz-2);
            dfs(i);
        }
    }
    cout<<kon;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

count_triplets.cpp:3: warning: ignoring '#pragma optimize GCC' [-Wunknown-pragmas]
    3 | #pragma optimize GCC ("Ofast")
      | 
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:94:13: warning: unused variable 'j' [-Wunused-variable]
   94 |     int m,i,j;
      |             ^

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 8 / 8
• Subtask 9: 10 / 10