Submission #696409

#	Time	Username	Problem	Language	Result	Execution time	Memory
696409		Quan2003	Duathlon (APIO18_duathlon)	C++17	100 / 100	129 ms	42988 KiB

count_triplets

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 5e5 + 5;
int up[21][N + 1];
int dp[N + 1];
int a[N + 1];
int n,m,q;
long long res; 
vector<int>adj[N + 1];
vector<int>tadj[N + 1];
int trs,dsz,psz;
bool vis[N + 1]; 
int st[N + 1],low[N + 1];
int comsize = 0; 
void dfs(int u,int p){
    a[u] = low[u] = ++dsz;
    st[++psz] = u;
    comsize++; 
    for(int i = 0; i < tadj[u].size(); i++){
        int v = tadj[u][i];
        if(v == p) continue;
        if(!a[v]){
            dfs(v,u);
            low[u] = min(low[u] , low[v]);
            if( low[v] >= a[u]){
                int j = u;
                trs++;
                adj[u].push_back(trs);
               // adj[trs].push_back(u);
                while(j != v){
                    j = st[psz--];
                    adj[trs].push_back(j);
                   // adj[j].push_back(trs);
               } 
            }
        }
        else low[u] = min(a[v] , low[u]);
    }
}
void dfs_calc(int u){
     dp[u] = (u <= n);
     for(int i = 0; i  < adj[u].size(); i++){ 
          int v = adj[u][i];
           dfs_calc(v);
           dp[u] += dp[v];
           if(u > n) res = res - (long long) adj[u].size() * (dp[v] - 1) * dp[v]; 
     }
     if(u > n) res = res - (long long) adj[u].size() * (comsize - dp[u] - 1) * (comsize - dp[u]);
} 
int main(){
     scanf("%d%d",&n,&m);
     for(int i = 0; i < m; i++){
         int u,v; scanf("%d%d",&u,&v);
         tadj[u].push_back(v);
         tadj[v].push_back(u); 
     }
     trs = n;
     for(int i = 1; i <= n; i++){
        if(!a[i]){
             comsize = 0; 
             dfs(i,0);
             res += (long long) comsize * (comsize - 1) * (comsize - 2);
             dfs_calc(i);
        }
     }
     cout<<res<<endl; 
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i = 0; i < tadj[u].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs_calc(int)':
count_triplets.cpp:45:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |      for(int i = 0; i  < adj[u].size(); i++){
      |                     ~~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:54:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |      scanf("%d%d",&n,&m);
      |      ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:56:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |          int u,v; scanf("%d%d",&u,&v);
      |                   ~~~~~^~~~~~~~~~~~~~

• 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