Submission #231823

#	Time	Username	Problem	Language	Result	Execution time	Memory
231823		ChrisT	Duathlon (APIO18_duathlon)	C++17	100 / 100	184 ms	58276 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pib = pair<int,bool>;
using ll = long long;
using pll = pair<ll,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
#ifdef fread_unlocked
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#endif
#define lc ind<<1
#define rc ind<<1|1
const int MN = 5e5+3;
vector<int> oadj[MN], adj[MN]; vector<vector<int>> comps; stack<int> st;
bool art[MN], vis[MN]; int over[MN], n, csz, dep[MN], p[MN], subsz[MN], sz[MN]; ll ans;
void dfs (int cur, int par = -1) {
	st.push(cur); int cnt = 0;
	for (int i : oadj[cur]) if (i != par) {
		if (!dep[i]) {
			dep[i] = dep[cur] + 1;
			int before = over[cur];
			dfs(i,cur);
			over[cur] += over[i];
			if (before == over[cur]) {
				art[cur] = ~par || cnt++;
				comps.push_back({cur});
				while (comps.back().back() != i) comps.back().push_back(st.top()), st.pop();
			}
		} else if (dep[i] < dep[cur]) ++over[par], --over[i];
	}
}
void dfs3 (int cur, int par = -1) {
	csz+=sz[cur]; vis[cur] = 1;
	for (int i : adj[cur]) if (i != par) dfs3(i,cur);
}
void dfs2 (int cur, int par = -1) {
	subsz[cur] = sz[cur];
	for (int i : adj[cur]) if (i != par) {
		dfs2(i,cur);
		subsz[cur] += subsz[i];
	}
	if (art[cur]) return;
	int dont = !!(~par); //we dont want to consider our parent articulation point, it was already considered by its parent
	//printf ("cur %d sz %d subsz %d dont %d\n",cur,sz[cur],subsz[cur],dont);
	//the only one we take here is B
	ans += (sz[cur]-dont) * 1LL * (subsz[cur]-sz[cur]) * 1LL * (csz-subsz[cur]);//printf ("adding %d*%d*%d\n",sz[cur]-dont,(subsz[cur]-sz[cur]),csz-subsz[cur]);
	//take all 3 here
	ans += (sz[cur]) * 1LL * (sz[cur]-1) * 1LL * (sz[cur]-2)/2;//printf ("adding %d*%d*%d/2\n",sz[cur]-dont,sz[cur]-1,sz[cur]-2);
	//take 2 here
	//printf ("adding %d*%d*%d\n",sz[cur]-1,sz[cur]-1-dont,csz-sz[cur]);
	if (!dont) ans += (sz[cur]-1) * 1LL * (sz[cur]-1) * 1LL * (csz - sz[cur]);
	else ans += (sz[cur]-1) * 1LL * (sz[cur]-2) * 1LL * (csz-subsz[cur]) + (sz[cur]-1) * 1LL * (sz[cur]-1) * 1LL * (subsz[cur]-sz[cur]);
	int sofar = 0;
	for (int i : adj[cur]) if (i != par) {
		ans += subsz[i] * 1LL * (sz[cur]) * 1LL * sofar;
		int nest = 0;
		for (int j : adj[i]) if (j != cur) {
			ans += (subsz[j]-1) * 1LL * nest;
			nest += (subsz[j]-1);
		}
		//printf ("adding %d*%d*%d\n",subsz[i],sz[cur]-dont,sofar);
		sofar += subsz[i];
	}
}
void print () {
	printf ("-----------COMPS------------\n");
	for (vector<int>&v : comps) {
		for (int i : v) printf ("%d ",i);
		printf ("\n");
	}
	printf ("---------------------------\n");
}
int main() {
	int m;
	scanf ("%d %d",&n,&m);
	while (m--) {
		int a,b; scanf ("%d %d",&a,&b);
		oadj[a].push_back(b); oadj[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) if (!dep[i]) {
		dep[i]=1;
		dfs(i);
	}
	int nn = 0;
	for (vector<int> &v : comps) {
		int id = ++nn;
		while (art[id]) id=++nn;
		//printf ("id %d: ",id);
		//for (int i : v) printf ("%d ",i);
		//printf ("\n");
		sz[id] = v.size();
		for (int j : v) if (art[j]) adj[id].push_back(j), adj[j].push_back(id);
	}
	for (int i = 1; i <= n; i++) if (art[i]) sz[i] = -(int)adj[i].size() + 1;
	for (int i = 1; i <= nn; i++) if (!vis[i] && !art[i]) {
		csz=0;
		dfs3(i);
		dfs2(i);
	}
	printf ("%lld\n",ans<<1);
	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d",&n,&m);
  ~~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:79:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a,b; scanf ("%d %d",&a,&b);
            ~~~~~~^~~~~~~~~~~~~~~

• 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