Submission #48979

#	Time	Username	Problem	Language	Result	Execution time	Memory
48979		yusufake	Duathlon (APIO18_duathlon)	C++98	31 / 100	194 ms	20892 KiB

count_triplets

#include<bits/stdc++.h> 
using namespace std; 

#define pb push_back
typedef long long ll; 
typedef pair < int , int > pp; 
const int mod = 1e9 + 7; 
const int N   = 3e5 + 5; 

vector < int > V[N]; 

ll AP[N],D[N],low[N],T,low2[N],D2[N],sz[N],n,m,i,x,y,nn,asd;
stack < int > S; 

void f(int x, int p){
    D2[x] = low2[x] = ++T;
    sz[x] = 1;
	S.push(x);
	for(auto y : V[x]){
		if(!D2[y]){
			f(y,x);
            low2[x] = min(low2[x] , low2[y]);
			sz[x] += sz[y];
			if(low2[y] >= D2[x]){
				ll t=0,a=0,ss=0;
				for(; S.top() != x ;){
					int z = S.top();
					S.pop();
					if(AP[z]) { ss += sz[z]-1; t += sz[z] * (sz[z]-1); }
					a++;
                    ss++;
				}
				asd -= a * t;
				asd -= a * (nn-ss) * (nn-ss-1);
			}
		}
        else if(y != p) low2[x] = min(low2[x] , D2[y]);
    }	
}

int ap;
void g(int x, int p){
    D[x] = low[x] = ++T; nn++;
	AP[x] = p == -1 ? -1 : 0;
	for(auto y : V[x]){
		if(!D[y]){
			g(y,x);
			low[x] = min(low[x] , low[y]);
			if(low[y] >= D[x]) AP[x]++;
        }
		else if(y != p) low[x] = min(low[x] , D[y]);
	}	
    if(AP[x]) ap=x;
}
int main(){
  cin >> n >> m;
  for(;m--;){
  	scanf("%d%d",&x,&y);
  	V[x].pb(y); V[y].pb(x);
  }
  
  for(i=1;i<=n;i++)
  	if(!D[i]){
  		nn = ap = 0; g(i,-1);
  		asd += nn * (nn-1) * (nn-2);
        for(;S.size();) S.pop();
  		if(ap) f(ap,-1);
  	}
    
    cout << asd;
    return 0;
}    

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:58:22: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
    scanf("%d%d",&x,&y);
                 ~~   ^
count_triplets.cpp:58:22: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll* {aka long long int*}' [-Wformat=]
count_triplets.cpp:58:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d",&x,&y);
    ~~~~~^~~~~~~~~~~~~~

• 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