Submission #791944

#	Time	Username	Problem	Language	Result	Execution time	Memory
791944		Lyrically	Duathlon (APIO18_duathlon)	C++17	100 / 100	104 ms	31132 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
int read(){int x;scanf("%lld",&x);return x;}
void print(int x){printf("%lld\n",x);}
void file(string s)
{
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
const int mod=998244353;
int n,m,tot,cnt,all;
int w[200005];
vector<int> edge[100005],g[200005];
int low[100005],dfn[100005];
stack<int> stk;
void tarjan(int x)
{
	dfn[x]=low[x]=++tot;stk.push(x);
	all++;
	for(int to:edge[x])
	{
		if(dfn[to]){low[x]=min(low[x],dfn[to]);}
		else
		{
			tarjan(to);
			low[x]=min(low[x],low[to]);
			if(low[to]==dfn[x])
			{
				cnt++;
				while(!stk.empty())
				{
					int y=stk.top();stk.pop();
					g[cnt].pb(y);
					g[y].pb(cnt);
					w[cnt]++;
					if(y==to){break;}
				}
				g[cnt].pb(x);
				g[x].pb(cnt);
				w[cnt]++;
			}
		}
	}
}
int res;
int sz[200005];
void dfs(int x,int fa)
{
	sz[x]=(x<=n);
	for(int to:g[x])
	{
		if(to==fa){continue;}
		dfs(to,x);
		res+=2*w[x]*sz[x]*sz[to];
		sz[x]+=sz[to];
	}
	res+=2*w[x]*sz[x]*(all-sz[x]);
}
signed main()
{
	n=read(),m=read();cnt=n;
	rep1(i,n){w[i]=-1;}
	rep1(i,m)
	{
		int u=read(),v=read();
		edge[u].pb(v),edge[v].pb(u);
	}
	rep1(i,n)
	{
		if(!dfn[i])
		{
			all=0;
			while(!stk.empty()){stk.pop();}
			tarjan(i);
			dfs(i,0);
		}
	}
	print(res);
	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'long long int read()':
count_triplets.cpp:8:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | int read(){int x;scanf("%lld",&x);return x;}
      |                  ~~~~~^~~~~~~~~~~
count_triplets.cpp: In function 'void file(std::string)':
count_triplets.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((s+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  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