Submission #681593

#	Time	Username	Problem	Language	Result	Execution time	Memory
681593		MilosMilutinovic	Duathlon (APIO18_duathlon)	C++14	100 / 100	159 ms	36052 KiB

count_triplets

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;

typedef long long ll;

const int N = 200200;
int n, m;
int ed[N][2];
vector<int> g[N];
bool art[N];
int h[N];
int minH[N];
vector<int> G[2 * N];
int cc;
int q[N];
int topQ;
ll ANS;
int cntVer;
int sz[2 * N];

int getOther(int i, int x) {
	return x ^ ed[i][0] ^ ed[i][1];
}

void addEdge(int v, int u) {
//	printf("new edge %d %d\n", v, u);
	G[v].push_back(u);
	G[u].push_back(v);
}

void dfsArt(int v, int par) {
	minH[v] = h[v];
	q[++topQ] = v;
	cntVer++;
	for (int i : g[v]) if (i != par) {
		int u = getOther(i, v);
		if (h[u] == -1) {
			h[u] = h[v] + 1;
			dfsArt(u, i);
			minH[v] = min(minH[v], minH[u]);
			if (minH[u] >= h[v]) {
				while(G[n + cc].empty() || G[n + cc].back() != u) {
					addEdge(n + cc, q[topQ--]);
				}
				addEdge(n + cc, v);
				cc++;
			}
		} else minH[v] = min(minH[v], h[u]);
	}
}

void dfsCalc(int v, int par) {
	if (v < n) sz[v] = 1;
	for (int u : G[v]) if (u != par) {
		dfsCalc(u, v);
		sz[v] += sz[u];
		if (v >= n)
			ANS -= (ll)(G[v].size() - 1) * (ll)sz[u] * (sz[u] - 1);
	}
	if (v >= n)
		ANS -= (ll)(G[v].size() - 1) * (ll)(cntVer - sz[v]) * (cntVer - sz[v] - 1);
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < 2; j++) {
			scanf("%d", &ed[i][j]);
			ed[i][j]--;
			g[ed[i][j]].push_back(i);
		}
	}
	for (int i = 0; i < n; i++)
		h[i] = -1;
	for (int i = 0; i < n; i++) {
		if (h[i] == -1) {
			h[i] = 0;
			cntVer = 0;
			dfsArt(i, -1);
			dfsCalc(i, -1);
			ANS += (ll)sz[i] * (sz[i] - 1) * (sz[i] - 2);

		}
	}
	printf("%lld\n", ANS);

	return 0;
}

/*
4 3
1 2
2 3
3 4
*/

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
count_triplets.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |    scanf("%d", &ed[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~

• 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