Submission #563090

#	Time	Username	Problem	Language	Result	Execution time	Memory
563090		Bill_00	Duathlon (APIO18_duathlon)	C++14	31 / 100	1031 ms	65452 KiB

count_triplets

#include <bits/stdc++.h>
#define N 1000000
#define INF 1000000007
#define ff first
#define ss second
typedef long long ll;
using namespace std;

bool vis[N], bridge[N], zam[100][100], cnt[15][15][15];
ll n, m, low[N], tin[N], h[N], sub[N], sz[N], timer, all, ans;
vector<pair<ll, ll> > adj[N];
vector<ll> adjt[N];

void dfs(ll node, ll par = 0){
	timer++;
	vis[node] = 1;
	tin[node] = timer;
	low[node] = tin[node];
	for(pair<ll, ll> child: adj[node]){
		ll to = child.ff;
		if(to == par) continue;
		if(vis[to] == 1){
			low[node] = min(low[node], tin[to]);
		}
		else{
			dfs(to, node);
			low[node] = min(low[node], low[to]);
			if(low[to] > tin[node]){
				bridge[child.ss] = 1;
			}
		}
	}
}

void dfs1(ll node, ll head){
	h[node] = head;
	vis[node] = 1;
	sz[head]++;
	for(pair<ll, ll> neigh : adj[node]){
		if(bridge[neigh.ss] == 1 && vis[neigh.ff] == 0){
			adjt[neigh.ff].push_back(head);
			adjt[head].push_back(neigh.ff);
			dfs1(neigh.ff, neigh.ff);
		}
		else{
			if(vis[neigh.ff] == 0){
				dfs1(neigh.ff, head);
			}
		}
	}
}
void dfs2(ll node, ll par = 0){
	// cout << node << ' ' << par << '\n';
	vis[node] = 1;
	sub[node] = sz[node];
	for(ll to : adjt[node]){
		if(to == par) continue;
		dfs2(to, node);
		sub[node] += sub[to];
	}
	// cout << sub[node] << ' ' << node << '\n';
}
void solve(ll node, ll par = 0){
	ll g = 0, h = 0;
	for(ll to : adjt[node]){
		if(to == par) continue;
		g += sub[to];
		h += (sub[to] * sub[to]);
	}
	ans += ((g * g - h + (all - sub[node]) * g * 2) * sz[node]);
	ans += (sz[node] * (sz[node] - 1) * (sz[node] - 2));
	ans += (2 * (sz[node] - 1) * (sz[node] - 1) * (all - sz[node]));
	for(ll to : adjt[node]){
		if(to == par) continue;
		solve(to, node);
	}
}

void subtask1(){
	int x[15];
	for(int i = 1; i <= n; i++) x[i] = i;
	do{
		int last = n;
		for(int i = 2; i <= n; i++){
			if(zam[x[i]][x[i - 1]] != 1){
				last = i - 1;
				break;
			}
		}
		for(int i = 1; i <= last; i++){
			for(int j = i + 1; j <= last; j++){
				for(int k = j + 1; k <= last; k++){
					if(cnt[x[i]][x[j]][x[k]] == 0){
						ans++;
						cnt[x[i]][x[j]][x[k]] = 1;
					}
				}
			}
		}
	}while(next_permutation(x + 1, x + n + 1));
	cout << ans;
}
int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	
    cin >> n >> m;
    for(ll i = 1; i <= m; i++){
    	ll x, y;
    	cin >> x >> y;
    	if(x <= 10 && y <= 10){
    		zam[x][y] = 1;
    		zam[y][x] = 1;
    	}
    	adj[x].push_back({y, i});
    	adj[y].push_back({x, i});
    }
    if(n <= 10){
    	subtask1();
    	return 0;
    }
    for(ll i = 1; i <= n; i++){
    	if(vis[i] == 0){
    		dfs(i);
    	}
    }
    memset(vis, 0, sizeof(vis));
    for(ll i = 1; i <= n; i++){
    	if(vis[i] == 0){
    		dfs1(i, i);
    	}
    }
    memset(vis, 0, sizeof(vis));
    for(ll i = 1; i <= n; i++){
    	if(vis[h[i]] == 0){
    		dfs2(h[i]);
    		all = sub[h[i]];
    		solve(h[i]);
    	}
    }
    cout << ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 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