Submission #659446

#	Time	Username	Problem	Language	Result	Execution time	Memory
659446		activedeltorre	Duathlon (APIO18_duathlon)	C++14	31 / 100	146 ms	29512 KiB

count_triplets

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
long long sef[100005];
long long sz[100005];
long long fre[100005];
long long lvl[100005];
long long best[100005];
long long parent[100005];
vector<long long >adj[100005];
vector<long long>adi[100005];
long long find (long long u)
{
    if(sef[u]==u)
    {
        return u;
    }
    return sef[u]=find(sef[u]);
}
long long merge (long long a,long long b)
{
    a=find(a);
    b=find(b);
    if(a!=b)
    {
        if(sz[a]<sz[b])
        {
            swap(a,b);
        }
        sef[b]=a;
        sz[a]=sz[a]+sz[b];
        sz[b]=0;
        return 1;
    }
    return 0;
}
struct str
{
    long long a,b,poz,folos=0;
};
str edges[200005];
long long numarconex[100005];
long long numar=0;
vector<long long>vec;
void dfs(long long curr,long long par)
{
    vec.push_back(curr);
    parent[curr]=par;
    lvl[curr]=lvl[par]+1;
    fre[curr]=1;
    best[curr]=lvl[curr];
    numar++;
    long long i,k;
    for(i=0; i<adj[curr].size(); i++)
    {
        k=adj[curr][i];
        if(fre[k]==0)
        {
            dfs(k,curr);
        }
        else if(k!=par)
        {
            best[curr]=min(best[curr],lvl[k]);
        }
    }
}
bool cmp(long long a,long long b)
{
    return lvl[a]>lvl[b];
}
long long v[100005];
long long suma=0;
long long subtree[100005];
long long n;
long long total;
void dfs2(long long curr,long long parent)
{
    long long i,k,rest,temp;
    temp=0;
    for(i=0; i<adi[curr].size(); i++)
    {
        k=adi[curr][i];
        if(k!=parent)
        {
            dfs2(k,curr);
            subtree[k]=subtree[k]+sz[k];
            subtree[curr]=subtree[curr]+subtree[k];
        }
    }
    rest=numarconex[curr]-sz[curr]-subtree[curr];
    for(i=0; i<adi[curr].size(); i++)
    {
        k=adi[curr][i];
        if(k!=parent)
        {
            suma=suma-sz[curr]*(subtree[k])*(subtree[k]-1);
            suma=suma-(sz[curr]-1)*subtree[k]*2;
        }
    }
    suma=suma-sz[curr]*(rest)*(rest-1);
    suma=suma-(sz[curr]-1)*rest*2;
   // cout<<curr<<" "<<temp<<'\n';
}
int capitan[100005];
int main()
{
    long long i,j,k,l,a,b,m;
    cin>>n>>m;
    for(i=1; i<=n; i++)
    {
        sef[i]=i;
        sz[i]=1;
    }
    for(i=1; i<=m; i++)
    {
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(i=1; i<=n; i++)
    {
        if(fre[i]==0)
        {
            numar=0;
            vec.clear();
            dfs(i,0);
            capitan[i]=1;
            for(j=0; j<vec.size(); j++)
            {
                numarconex[vec[j]]=numar;
            }
        }
    }
    int cnt=0;
    for(i=1; i<=n; i++)
    {
        if(fre[i]==0)
        {
            cnt++;
        }
    }
    if(cnt!=0)
    {
        cout<<2/0;
    }
    for(i=1; i<=n; i++)
    {
        v[i]=i;
    }
    sort(v+1,v+n+1,cmp);
    for(i=1; i<=n; i++)
    {
        if(best[v[i]]<=lvl[v[i]]-1)
        {
            best[parent[v[i]]]=min(best[v[i]],best[parent[v[i]]]);
            merge(v[i],parent[v[i]]);
        }
    }
    for(i=1; i<n; i++)
    {
        a=find(v[i]);
        b=find(parent[v[i]]);
        if(a!=b && capitan[a]==0)
        {
            adi[a].push_back(b);
            adi[b].push_back(a);
        }
    }
    for(i=1; i<=n; i++)
    {
        if(capitan[i]==1)
        {
            suma=suma+numarconex[i]*(numarconex[i]-1)*(numarconex[i]-2);
            dfs2(find(i),0);
        }
    }
    cout<<suma;
    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs(long long int, long long int)':
count_triplets.cpp:56:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(i=0; i<adj[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(long long int, long long int)':
count_triplets.cpp:82:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(i=0; i<adi[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
count_triplets.cpp:93:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(i=0; i<adi[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
count_triplets.cpp:80:24: warning: variable 'temp' set but not used [-Wunused-but-set-variable]
   80 |     long long i,k,rest,temp;
      |                        ^~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:130:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |             for(j=0; j<vec.size(); j++)
      |                      ~^~~~~~~~~~~
count_triplets.cpp:146:16: warning: division by zero [-Wdiv-by-zero]
  146 |         cout<<2/0;
      |               ~^~
count_triplets.cpp:109:19: warning: unused variable 'k' [-Wunused-variable]
  109 |     long long i,j,k,l,a,b,m;
      |                   ^
count_triplets.cpp:109:21: warning: unused variable 'l' [-Wunused-variable]
  109 |     long long i,j,k,l,a,b,m;
      |                     ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 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