Submission #407766

#	Time	Username	Problem	Language	Result	Execution time	Memory
407766		oolimry	Duathlon (APIO18_duathlon)	C++17	100 / 100	219 ms	30388 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define show3(x, y, z) cerr << #x << " is " << x << ", " << #y << " is " << y << ", " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<int, int> ii;

int n, m; 
int low[100005];
int depth[100005];
vector<int> adj[100005];
vector<int> tree[200005];
int cnt;
stack<int> S;
lint num = 0;
void tarjan(int u){
	low[u] = depth[u];
	S.push(u);
	num++;
	for(int v : adj[u]){
		if(low[v] == 0){ ///not visisted
			depth[v] = depth[u]+1;
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if(low[v] >= depth[u]){
				while(true){
					int nv = S.top();
					tree[cnt].push_back(nv);
					tree[nv].push_back(cnt);
					S.pop();
					if(nv == v) break;
				}
				tree[cnt].push_back(u);
				tree[u].push_back(cnt);
				cnt++;
			}
		}
		else if(depth[v] != depth[u]-1) low[u] = min(low[u], depth[v]);
	}
}

lint ans = 0;
lint sz[200005];
lint weight[200005];
void dfs(int u, int p){
	sz[u] = (u <= n);
	if(u <= n) weight[u] = -1;
	else weight[u] = sz(tree[u]);
	for(int v : tree[u]){
		if(v != p){
			dfs(v, u);
	
			ans += weight[u] * (2LL * sz[v] * sz[u]);
			sz[u] += sz[v];
		}
	}
	
	ans += weight[u] * (2LL * sz[u] * (num-sz[u]));
}


int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> m;
	cnt = n+1;
	
	for(int i = 1;i <= m;i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	for(int i = 1;i <= n;i++){
		if(depth[i] == 0){
			depth[i] = 1; num = 0; while(not S.empty()) S.pop();
			tarjan(i);
			dfs(i, 0);
		}
	}
	
	cout << ans;
}

• 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