Submission #1070946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070946		pawned	Duathlon (APIO18_duathlon)	C++17	23 / 100	52 ms	23572 KiB

count_triplets

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

const char nl = '\n';

void fastIO() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}

const int MAX = 1e5 + 5;

int N, M;

bool vis[MAX];
vi adj[MAX];

vi kids[MAX];	// all below
ll sz[MAX];	// size of below
ll sumd[MAX];	// sum of all dists below

void dfs(int n) {
	vis[n] = true;
	sz[n] = 1;
	for (int x : adj[n]) {
		if (!vis[x]) {
			dfs(x);
			kids[n].pb(x);
			sz[n] += sz[x];
			sumd[n] += (sumd[x] + sz[x]);
		}
	}
}

int main() {
	fastIO();
	cin>>N>>M;
	for (int i = 0; i < M; i++) {
		int u, v;
		cin>>u>>v;
		u--; v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for (int i = 0; i < N; i++) {
		if (!vis[i]) {
			dfs(i);
		}
	}
/*	cout<<"sz: ";
	for (int i = 0; i < N; i++) {
		cout<<sz[i]<<" ";
	}
	cout<<endl;
	cout<<"sumd: ";
	for (int i = 0; i < N; i++) {
		cout<<sumd[i]<<" ";
	}
	cout<<endl;*/
	ll total = 0;
	for (int i = 0; i < N; i++) {
		ll sum = 0;
//		cout<<"at "<<i<<endl;
		sum += (sumd[i] - sz[i] + 1);	// go down
//		cout<<"straight down: "<<(sumd[i] - sz[i] + 1)<<endl;
		ll sum1 = 0;	// total of all (sumd + sz) below
		ll sum2 = 0;	// total of all sumd^2 below
		ll sum3 = 0;	// total of all sz below
		ll sum4 = 0;	// total of all sz^2 below
		ll sum5 = 0;	// tota of all (sumd + sz) * sz below
		for (int x : kids[i]) {
			sum1 += (sumd[x] + sz[x]);
			sum2 += (sumd[x] * sumd[x]);
			sum3 += sz[x];
			sum4 += (sz[x] * sz[x]);
			sum5 += ((sumd[x] + sz[x]) * sz[x]);
		}
//		cout<<"sums: "<<sum1<<" "<<sum2<<" "<<sum3<<" "<<sum4<<" "<<sum5<<endl;
		sum += (sum1 * sum3 - sum5);
		sum -= (sum3 * sum3 - sum4) / 2;
/*		cout<<"adding "<<(sum1 * sum3 - sum5)<<endl;
		cout<<"subtracting "<<(sum3 * sum3 - sum4) / 2<<endl;
		cout<<"sum: "<<sum<<endl;*/
		total += sum;
	}
//	cout<<"ANSWER: ";
	cout<<total * 2<<endl;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10