Submission #1108970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108970		simona1230	Duathlon (APIO18_duathlon)	C++17	0 / 100	62 ms	38728 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

int n,m;
vector<int> v[100001];
void read()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

int t,in[100001],low[100001],used[100001];
int art[100001];

void dfsart(int i,int p)
{
    used[i]=1;
    in[i]=t++;
    low[i]=in[i];
    int c=0;

    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(nb==p)continue;

        if(!used[nb])
        {
            c++;
            dfsart(nb,i);
            low[i]=min(low[i],low[nb]);
            if(p!=-1&&in[i]<=low[nb])
                art[i]=1;

        }
        else low[i]=min(low[i],in[nb]);
    }

    if(p==-1&&c>1)
        art[i]=1;
}

int c[100001],num;

void part(int i)
{
    c[i]=num;
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(c[nb]||art[nb])continue;

        part(nb);
    }
}

vector<int> g[100001];

bool cmp(int i,int j)
{
    return c[i]<c[j];
}

void construct()
{
    num=n;
    for(int i=1;i<=n;i++)
    {
        if(!c[i]&&!art[i])
        {
            num++;
            part(i);
        }
        //cout<<c[i]<<" ";
    }
    //cout<<endl;

    for(int i=1;i<=n;i++)
    {
        if(c[i])
        {
            //cout<<i<<" 1 "<<c[i]<<endl;
            g[i].push_back(c[i]);
            g[c[i]].push_back(i);
        }
        else
        {
            sort(v[i].begin(),v[i].end(),cmp);
            for(int j=0;j<v[i].size();j++)
            {
                int nb=v[i][j];
                if(c[nb]&&(j==0||c[nb]!=c[v[i][j-1]]))
                {
                    //cout<<i<<" 2 "<<c[nb]<<endl;
                    g[i].push_back(c[nb]);
                    g[c[nb]].push_back(i);
                }
                else if(!c[nb]&&nb>i)
                {
                    num++;
                    //cout<<i<<" 3 "<<num<<endl;
                    g[i].push_back(num);
                    g[num].push_back(i);
                    //cout<<nb<<" 4 "<<num<<endl;

                    g[nb].push_back(num);
                    g[num].push_back(nb);
                }
            }
        }
    }
}

int sz[100001];
int ans;

int used1[100001];

void dfs(int i,int p)
{
    used1[i]=1;
    if(i<=n)sz[i]=1;
    for(int j=0;j<g[i].size();j++)
    {
        int nb=g[i][j];
        if(nb==p)continue;

        dfs(nb,i);
        sz[i]+=sz[nb];
    }

    //cout<<i<<" > "<<sz[i]<<endl;

    if(!art[i])return;

    for(int j=0;j<g[i].size();j++)
    {
        int nb=g[i][j];
        if(nb==p)continue;

        int avail=(sz[nb]+1)*sz[nb];
        int outside=n-sz[nb]-1;
        ans-=avail*outside;
    }

    int avail=(n-sz[i]+1)*(n-sz[i]);
    int outside=sz[i]-1;
    ans-=avail*outside;
}

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

	read();
	for(int i=1;i<=n;i++)
    {
        if(!used[i])dfsart(i,-1);
    }
    construct();
    ans=n*(n-1)*(n-2);

    for(int i=1;i<=n;i++)
        if(!used1[i])dfs(i,-1);

    cout<<ans<<endl;

	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfsart(int, int)':
count_triplets.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
count_triplets.cpp: In function 'void part(int)':
count_triplets.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
count_triplets.cpp: In function 'void construct()':
count_triplets.cpp:96:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             for(int j=0;j<v[i].size();j++)
      |                         ~^~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:130:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     for(int j=0;j<g[i].size();j++)
      |                 ~^~~~~~~~~~~~
count_triplets.cpp:143:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for(int j=0;j<g[i].size();j++)
      |                 ~^~~~~~~~~~~~

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