Submission #734117

#	Time	Username	Problem	Language	Result	Execution time	Memory
734117		Username4132	Duathlon (APIO18_duathlon)	C++14	23 / 100	1098 ms	1048576 KiB

count_triplets

#include<iostream>
#include<vector>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define PB push_back

const int MAXN=100010;
int n, m, curSz, si[MAXN];
bool vis[MAXN];
ll ans=0;
vector<int> g[MAXN], roots;

void dfs1(int v){
    vis[v]=true;
    for(int to:g[v]) if(!vis[to]) dfs1(to);
}

void dfs2(int v, int p){
    si[v]=1;
    for(int to:g[v]) if(to!=p){
        dfs2(to, v);
        si[v]+=si[to];
    }
}

void dfs3(int v, int p){
    ll sq=0;
    for(int to:g[v]) if(to!=p){
        sq+=((ll)si[to])*si[to];
        dfs3(to, v);
    }
    sq+=((ll)(curSz-si[v]))*(curSz-si[v]);
    sq=((ll)(curSz-1))*(curSz-1) - sq;
    ans+=sq;
}

int main(){
    scanf("%d %d", &n, &m);
    forn(i, m){
        int a, b; scanf("%d %d", &a, &b); --a, --b;
        g[a].PB(b), g[b].PB(a);
    }

    forn(i, n) if(!vis[i]) dfs1(i), roots.PB(i);
    for(auto ro:roots) dfs2(ro, ro);
    for(auto ro:roots){
        curSz = si[ro];
        dfs3(ro, ro);
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:41:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         int a, b; scanf("%d %d", &a, &b); --a, --b;
      |                   ~~~~~^~~~~~~~~~~~~~~~~

• 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