Submission #421238

#	Time	Username	Problem	Language	Result	Execution time	Memory
421238		Blagojce	Duathlon (APIO18_duathlon)	C++11	31 / 100	320 ms	103072 KiB

count_triplets

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
 
mt19937 _rand(time(NULL));
const int mxn = 5e5+5;

int n, m;

vector<pii> g[mxn];

bool vis[mxn];
int low[mxn];
int pre[mxn];

ll artin[mxn];

int pos = 0;

vector<int> art;

stack<int> S;

vector<vector<int> > G;

bool adds[mxn];

void dfs(int u, int p){
	vis[u] = true;
	pre[u] = low[u] = pos ++;
	
	int c = 0;
	for(auto e : g[u]){
		if(e.st == p) continue;
		
		if(!adds[e.nd]){
			adds[e.nd] = true;
			S.push(e.nd);
		}
		if(vis[e.st]){
			low[u] = min(low[u], pre[e.st]);
		}
		else{
			++c;
			dfs(e.st, u);
			low[u] = min(low[u], low[e.st]);
			if(low[e.st] >= pre[u] && p != -1){
				art.pb(u);
			}
			if((low[e.st] >= pre[u] && p != -1) || (p == -1 && c > 1)){
				vector<int> comp;
				while(S.top() != e.nd){
					comp.pb(S.top());
					S.pop();
				}
				comp.pb(e.nd);
				S.pop();
				G.pb(comp);
			}
		}
	}
	if(p == -1 && c > 1){
		art.pb(u);
	}
}

void decompose(){
	fr(i, 0, n){
		if(vis[i]) continue;
		dfs(i, -1);
		vector<int> lst;
		while(!S.empty()){
			lst.pb(S.top());
			S.pop();
		}
		G.pb(lst);
	}
	sort(all(art));
	art.erase(unique(all(art)), art.end());
}

vector<pii> edge;

set<int> inter[mxn];

ll sz[mxn];


vector<int> tree[mxn];
ll totsum = 0;

ll cs(int u, int p){
	ll ret = sz[u];
	for(auto e : tree[u]){
		if(e == p) continue;
		ret += cs(e, u);
	}
	return ret;
}


int build_tree(){
	int id = 0;
	for(auto u : G){
		set<int> ver;
		for(auto e : u){
			int a = edge[e].st;
			int b = edge[e].nd;
			inter[a].insert(id);
			inter[b].insert(id);
			ver.insert(a);
			ver.insert(b);
		}
		
		sz[id] = (int)ver.size();
		++id;
	}
	for(auto a : art){
		sz[id] = 1;
		for(auto u : inter[a]){
			--sz[u];
			
			artin[u] ++;
			tree[id].pb(u);
			tree[u].pb(id);
		}
		++id;
	}
	return id;
}

ll sub[mxn];
ll ans = 0;


void dfst(int u){
	vis[u] = true;
	sub[u] = sz[u];
	
	vector<ll> V;
	
	for(auto e : tree[u]){
		if(vis[e]) continue;
		dfst(e);
		sub[u] += sub[e];
		V.pb(sub[e]);
	}
	V.pb(totsum-sub[u]);
	
	ll s = totsum - sz[u];
	
	ans += s*s*sz[u];
	for(auto e : V) ans -= e*e*sz[u];
	
	ll S = artin[u] + sz[u];
	
	if(S >= 3){
		ans += S*(S-1)*(S-2);
	}
	
	if(sz[u] >= 2){
		ans += (sz[u]*(sz[u]-1))*(s-artin[u])*2;
	}
}
	
void solve_tree(int k){
	memset(vis, false, sizeof(vis));
	fr(i, 0, k){
		if(vis[i]) continue;
		totsum = cs(i, i);
		dfst(i);
	}
}
void solve(){
	cin >> n >> m;
	fr(i, 0, m){
		int u, v;
		cin >> u >> v;
		--u, --v;
		
		g[u].pb({v, i});
		g[v].pb({u, i});
		edge.pb({u, v});
	}
	decompose();
	
	int k = build_tree();	
	
	solve_tree(k);
	
	cout<<ans<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}
/*
10 8
1 2
1 3
3 4
3 5
6 7
6 8
8 9
8 10
*/

• 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