Submission #374562

#	Time	Username	Problem	Language	Result	Execution time	Memory
374562		eulerdesoja	Duathlon (APIO18_duathlon)	C++14	100 / 100	135 ms	28392 KiB

count_triplets

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

#define ll long long
#define pb push_back
#define sz(x) int(x.size())

typedef pair<int,int>ii;
typedef vector<int> vi;

void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0); 
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str(),"w",stdout);
}
const int mxn=1e5+5;
int n,m,t,bcc=1,cnt,sz[2*mxn],in[mxn],low[mxn];
vi g[mxn],bg[2*mxn],stck;
ll ans;
void dfs(int i,int p){
	in[i]=low[i]=++t;
	stck.pb(i);
	cnt++;
	for(int j:g[i])if(j!=p){
		if(in[j])low[i]=min(low[i],in[j]);
		else{
			dfs(j,i);
			low[i]=min(low[i],low[j]);
			if(low[j]>=in[i]){
				bg[i].pb(n+bcc);
				while(bg[n+bcc].empty() || bg[n+bcc].back()!=j){
					bg[n+bcc].pb(stck.back());
					stck.pop_back();
				}
				bcc++;
			}
		}
	}
}
void dfs1(int i,int p){
	sz[i]=(i<=n);
	for(int j:bg[i])if(j!=p){
		dfs1(j,i);
		sz[i]+=sz[j];
		if(i>n)ans-=1ll*sz(bg[i])*sz[j]*(sz[j]-1);
	}
	if(i>n)ans-=1ll*sz(bg[i])*(cnt-sz[i])*(cnt-sz[i]-1);
}
int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	//setIO("sort");
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int x,y;cin>>x>>y;
		g[x].pb(y);
		g[y].pb(x);
	}
	for(int i=1;i<=n;i++){
		if(!in[i]){
			cnt=0;
			dfs(i,0);
			ans+=1ll*cnt*(cnt-1)*(cnt-2);
			dfs1(i,0);
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void setIO(std::string)':
count_triplets.cpp:14:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   14 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:15:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   15 |   freopen((s+".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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