제출 #483403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483403		8e7	Duathlon (APIO18_duathlon)	C++17	100 / 100	149 ms	48124 KiB

count_triplets

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <bitset>
#include <deque>
#include <stack>
#include <assert.h>
using namespace std;
void debug(){cout << endl;};
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define maxn 200005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn], tree[maxn], bcc[maxn];
int ti[maxn], low[maxn], cnt, t, id[maxn], siz[maxn], sub[maxn], artcnt[maxn], pa[maxn], root[maxn];
ll val[maxn];
bool art[maxn];
vector<int> stk;
void dfs(int n, int par) {
	low[n] = ti[n] = t++;
	stk.push_back(n);
	for (int v:adj[n]) {
		if (v != par) {
			if (ti[v]) low[n] = min(low[n], ti[v]);
			else {
				dfs(v, n);
				if (low[v] >= ti[n]) {
					cnt++;
					int x;
					do{
						x = stk.back(), stk.pop_back();
						bcc[x].push_back(cnt);
					} while (x != v);
					bcc[n].push_back(cnt);
				}
				low[n] = min(low[n], low[v]);
			}
		}
	}
}
bool vis[maxn];
void build(int n, int par, int r) {
	vis[n] = 1;
	root[n] = r;
	if (art[n]) sub[n] = 1;
	else sub[n] = siz[n];
	pa[n] = par;
	for (int v:tree[n]) {
		if (v != par) {
			build(v, n, r);
			sub[n] += sub[v] - 1;
		}
	}
	//debug(n, sub[n]);
}
int main() {
	io
	int n, m;
	cin >> n >> m;
	for (int i = 0;i < m;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	t = 1;
	for (int i = 1;i <= n;i++) {
		if (!ti[i]) stk.clear(), dfs(i, 0);
	}
	for (int i = 1;i <= n;i++) {
		if (!bcc[i].size()) continue;
		if (bcc[i].size() > 1) {
			cnt++;
			for (int v:bcc[i]) {
				tree[v].push_back(cnt);
				tree[cnt].push_back(v);	
				siz[v]++, artcnt[v]++;
			}
			id[i] = cnt;
			art[id[i]] = 1;
		} else {
			id[i] = bcc[i].back();	
			siz[bcc[i].back()]++;
		}
		//debug("id", i, id[i]);
	}
	for (int i = 1;i <= cnt;i++) {
		if (!vis[i]) build(i, 0, i);
	}
	for (int i = 1;i <= cnt;i++) {
		if (art[i]) continue;
		for (int v:tree[i]) {
			ll s = (v == pa[i] ? (sub[root[i]] - sub[i] + 1) : sub[v]);
			val[i] += s * (s - 1);
		}
	}
	ll ans = 0, prv = 0;
	for (int i = 1;i <= n;i++) {
		if (!bcc[i].size()) continue;
		int cur = id[i];
		ll tot = sub[root[cur]];
		ans += (tot - 1) * (tot - 2);
		if (art[cur]) {
			for (int v:tree[cur]) { 
				ll s = (v == pa[cur] ? sub[cur] : (tot - sub[v] + 1));
				ans -= val[v] - (s * (s - 1));
			}
		} else {
			ans -= val[cur];
		}
		//debug(i, ans - prv);
		prv = ans;
	}	
	cout << ans << endl;
}
/*
4 3
1 2
2 3
3 4

4 4
1 2
2 3
3 4
4 2

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

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

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:107:14: warning: variable 'prv' set but not used [-Wunused-but-set-variable]
  107 |  ll ans = 0, prv = 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