Submission #361325

#	Time	Username	Problem	Language	Result	Execution time	Memory
361325		hihi	Duathlon (APIO18_duathlon)	C++11	100 / 100	167 ms	29864 KiB

count_triplets

#include <cstdio>
#include <vector>
#include <algorithm>

const int MN = 100005;

int N, M, cnt;
std::vector<int> G[MN], T[MN * 2];
long long Ans;

int dfn[MN], low[MN], dfc, num;
int stk[MN], tp;

int wgh[MN * 2];

void Tarjan(int u) {
	low[u] = dfn[u] = ++dfc;
	stk[++tp] = u;
	++num;
	for (int v : G[u]) {
		if (!dfn[v]) {
			Tarjan(v);
			low[u] = std::min(low[u], low[v]);
			if (low[v] == dfn[u]) {
				wgh[++cnt] = 0;
				for (int x = 0; x != v; --tp) {
					x = stk[tp];
					T[cnt].push_back(x);
					T[x].push_back(cnt);
					++wgh[cnt];
				}
				T[cnt].push_back(u);
				T[u].push_back(cnt);
				++wgh[cnt];
			}
		} else low[u] = std::min(low[u], dfn[v]);
	}
}

int vis[MN * 2], siz[MN * 2];

void DFS(int u, int fz) {
	vis[u] = 1;
	siz[u] = (u <= N);
	for (int v : T[u]) if (v != fz) {
		DFS(v, u);
		Ans += 2ll * wgh[u] * siz[u] * siz[v];
		siz[u] += siz[v];
	}
	Ans += 2ll * wgh[u] * siz[u] * (num - siz[u]);
}

int main() {
	scanf("%d%d", &N, &M);
	for (int u = 1; u <= N; ++u) wgh[u] = -1;
	cnt = N;
	for (int i = 1; i <= M; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for (int u = 1; u <= N; ++u) if (!dfn[u]) {
		num = 0;
		Tarjan(u), --tp;
		DFS(u, 0);
	}
	printf("%lld\n", Ans);
	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:54:7: 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:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |   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