Submission #1112874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112874		VectorLi	철인 이종 경기 (APIO18_duathlon)	C++17	100 / 100	96 ms	35912 KiB

count_triplets

#include <bits/stdc++.h>
#define I64 long long

using namespace std;

const int V = (int) 1E5;

int S;
vector<int> A[V];

namespace VBCC {
	int n;
	int d[V], f[V], t;
	stack<int> s;
	vector<int> e[V];
	
	void add(int u, int v) {
		e[u].push_back(v);
		e[v].push_back(u);
	}
	
	void DFS(int u, int p) {
		d[u] = t;
		t = t + 1;
		f[u] = d[u];
		s.push(u);
		
		int c = 0;
		for (auto v : e[u]) {
			if (d[v] < 0) {
				c = c + 1;
				DFS(v, u);
				f[u] = min(f[u], f[v]);
				if (f[v] == d[u]) {
					int w;
					do {
						w = s.top();
						s.pop();
						A[S].push_back(w);
					} while (w != v);
					A[S].push_back(u);
					S = S + 1;
				}
			} else {
				f[u] = min(f[u], d[v]);
			}
		}
		
		if (p < 0 && c == 0) {
			A[S].push_back(u);
			S = S + 1;
		}
	}
	
	void run(int x) {
		n = x;
		fill(d, d + n, 0 - 1);
		for (int u = 0; u < n; u++) {
			if (d[u] < 0) {
				DFS(u, 0 - 1);
				s.pop();
			}
		}
	}
};

int n, m;

vector<int> e[V * 2];
int a[V * 2], s[V * 2], p[V * 2];
int t[V * 2];
I64 c;

void DFS(int u) {
	s[u] = (u < n);
	for (auto v : e[u]) {
		if (v != p[u]) {
			p[v] = u;
			t[v] = t[u];
			DFS(v);
			c = c + (I64) a[u] * s[v] * s[u] * 2;
			s[u] = s[u] + s[v];
		}
	}
}

void solve() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u = u - 1;
		v = v - 1;
		VBCC::add(u, v);
	}
	VBCC::run(n);
	
	for (int i = 0; i < S; i++) {
		int u = n + i;
		for (auto v : A[i]) {
			e[u].push_back(v);
			e[v].push_back(u);
		}
	}
	for (int u = 0; u < n; u++) {
		a[u] = 0 - 1;
	}
	for (int i = 0; i < S; i++) {
		a[i + n] = (int) A[i].size();
	}
	
	fill(p, p + n + S, 0 - 1);
	for (int u = 0; u < n + S; u++) {
		if (p[u] < 0) {
			p[u] = 0 - 1;
			t[u] = u;
			DFS(u);
		}
	}
	for (int u = 0; u < n + S; u++) {
		c = c + (I64) a[u] * s[u] * (s[t[u]] - s[u]) * 2;
	}
	cout << c << "\n";
} 

int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	solve();
	return 0;
}

• 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