Submission #659413

#	Time	Username	Problem	Language	Result	Execution time	Memory
659413		activedeltorre	Duathlon (APIO18_duathlon)	C++14	0 / 100	133 ms	26988 KiB

count_triplets

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

using namespace std;
int sef[100005];
int sz[100005];
int fre[100005];
int lvl[100005];
int best[100005];
int parent[100005];
vector<pair<int,int> >adj[100005];
vector<int>adi[100005];
int find (int u)
{
    if(sef[u]==u)
    {
        return u;
    }
    return sef[u]=find(sef[u]);
}
int merge (int a,int 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
{
    int a,b,poz,folos=0;
};
str edges[200005];
void dfs(int curr,int par)
{
    parent[curr]=par;
    lvl[curr]=lvl[par]+1;
    fre[curr]=1;
    best[curr]=lvl[curr];
    int i,k;
    for(i=0;i<adj[curr].size();i++)
    {
        k=adj[curr][i].first;
        if(fre[k]==0)
        {
            edges[adj[curr][i].second].folos=1;
            dfs(k,curr);
        }
        else if(k!=par)
        {
            best[curr]=min(best[curr],lvl[k]);
        }
    }
}
bool cmp(int a,int b)
{
    return lvl[a]>lvl[b];
}
int v[100005];
long long suma=0;
long long subtree[100005];
int n;
void dfs2(int curr,int parent)
{
    long long i,k,rest;
    for(i=0;i<adi[curr].size();i++)
    {
        k=adi[curr][i];
        if(k!=parent)
        {
            dfs2(k,curr);
            subtree[curr]=subtree[curr]+subtree[k]+sz[k];
        }
    }
   // for(i=0;i<special)
    rest=n-subtree[curr]-sz[curr];
    suma=suma+sz[curr]*(sz[curr]-1)*(sz[curr]-2);
    suma=suma+sz[curr]*(sz[curr]-1)*(rest)*2;
    suma=suma+sz[curr]*(sz[curr]-1)*(subtree[curr])*2;
    suma=suma+sz[curr]*(subtree[curr])*(rest)*2;
}
int main()
{
    int 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>>edges[i].a>>edges[i].b;
        edges[i].poz=i;
        edges[i].folos=0;
        adj[edges[i].a].push_back({edges[i].b,i});
        adj[edges[i].b].push_back({edges[i].a,i});
    }
    dfs(1,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)
        {
            merge(v[i],parent[v[i]]);
        }
    }
    for(i=1;i<n;i++)
    {
        a=find(v[i]);
        b=find(parent[v[i]]);
        if(a!=b)
        {
            adi[a].push_back(b);
            adi[b].push_back(a);
        }
    }
    dfs2(1,0);
    cout<<suma;
    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:51:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(i=0;i<adj[curr].size();i++)
      |             ~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(int, int)':
count_triplets.cpp:76:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(i=0;i<adi[curr].size();i++)
      |             ~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:94:11: warning: unused variable 'j' [-Wunused-variable]
   94 |     int i,j,k,l,a,b,m;
      |           ^
count_triplets.cpp:94:13: warning: unused variable 'k' [-Wunused-variable]
   94 |     int i,j,k,l,a,b,m;
      |             ^
count_triplets.cpp:94:15: warning: unused variable 'l' [-Wunused-variable]
   94 |     int i,j,k,l,a,b,m;
      |               ^

• 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