제출 #99856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99856		TadijaSebez	철인 이종 경기 (APIO18_duathlon)	C++11	100 / 100	308 ms	37496 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=200050;
vector<int> G[N],E[N];
void AddEdge(int u, int v){ E[u].pb(v);E[v].pb(u);}
int cnt,disc[N],low[N],tid,n,csz[N];
bool in[N];
stack<int> s;
void Tarjan(int u)
{
	disc[u]=low[u]=++tid;
	in[u]=1;s.push(u);
	for(int v:G[u])
	{
		if(!disc[v])
		{
			Tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=disc[u])
			{
				++cnt;
				AddEdge(u,cnt);
				csz[cnt]++;
				int h;
				do
				{
					h=s.top();
					s.pop();
					in[h]=0;
					AddEdge(h,cnt);
					csz[cnt]++;
				}while(h!=v);
			}
		}
		else if(in[v]) low[u]=min(low[u],disc[v]);
	}
}
ll ans;
int sz[N],dep[N],up[N];
void DFSSZ(int u, int p)
{
	sz[u]=u<=n;
	dep[u]=dep[p]+(u<=n);
	up[u]=n;
	for(int v:E[u]) if(v!=p) DFSSZ(v,u),sz[u]+=sz[v],up[u]-=sz[v];
}
int rt[N],par[N];
ll all[N],up_all[N],down_all[N];
void Solve(int u, int p, int root)
{
	par[u]=p;
	all[u]=(ll)(sz[root]-(u<=n))*(sz[root]-(u<=n)-1);
	all[u]-=(ll)(sz[root]-sz[u])*(sz[root]-sz[u]-1);
	for(int v:E[u]) if(v!=p) all[u]-=(ll)sz[v]*(sz[v]-1);
	down_all[u]=(ll)(sz[u]-(u<=n))*(sz[u]-(u<=n)-1);
	for(int v:E[u]) if(v!=p) down_all[u]-=(ll)sz[v]*(sz[v]-1);
	if(p) up_all[u]=all[p]-(ll)sz[u]*(sz[root]-(p<=n)-sz[u])*2;
	for(int v:E[u]) if(v!=p) Solve(v,u,root);
	if(u<=n)
	{
		ans+=all[u];
		for(int v:E[u]) if(v!=p) ans+=down_all[v];
		if(p) ans+=up_all[u];
	}
}
int main()
{
	int m,u,v;
	scanf("%i %i",&n,&m);
	cnt=n;
	for(int i=1;i<=m;i++) scanf("%i %i",&u,&v),G[u].pb(v),G[v].pb(u);
	vector<int> root;
	for(int i=1;i<=n;i++) if(!disc[i]) Tarjan(i),root.pb(i);
	for(int i:root) DFSSZ(i,0),Solve(i,0,i);
	printf("%lld\n",ans);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:73:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%i %i",&u,&v),G[u].pb(v),G[v].pb(u);
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

• 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