Submission #48882

#	Time	Username	Problem	Language	Result	Execution time	Memory
48882		khsoo01	Duathlon (APIO18_duathlon)	C++11	100 / 100	345 ms	26084 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 100005;

ll n, m, p[N], dfn[N], par[N], chi[N], cn, ans;
ll uni[N][2], bi[N][2], us[N], bs[N], st[N], mis[N];
bool vis[N][2], v2[N];

vector<ll> raw[N], adj[N];

ll Find (ll X) {
	if(p[X] == X) return X;
	return p[X] = Find(p[X]);
}

void dfst (ll C, ll P) {
	v2[C] = true;
	chi[C] = 1;
	par[C] = P;
	dfn[C] = ++cn;
	for(auto &T : raw[C]) {
		if(v2[T]) continue;
		dfst(T, C);
		chi[C] += chi[T];
	}
}

pair<ll,ll> conv (ll C, ll P) {
	if(par[C] == P) return {C, 0};
	else return {P, 1};
}

bool mnst (ll A, ll B) {
	if(B) return true;
	if(p[A] != A) return true;
	return false;
}

void calc (ll C, ll P) {
	ll A, B;
	tie(A, B) = conv(C, P);
	if(vis[A][B]) return;
	vis[A][B] = true;
	if(~mis[C]) {
		if(mis[C] == 0) {
			for(auto &T : adj[C]) {
				if(T == P) continue;
				calc(T, C);
				ll X, Y;
				tie(X, Y) = conv(T, C);
				us[C] += uni[X][Y];
				bs[C] += bi[X][Y];
			}
			mis[C] = P;
		}
		else if(mis[C] != P) {
			calc(mis[C], C);
			ll X, Y;
			tie(X, Y) = conv(mis[C], C);
			us[C] += uni[X][Y];
			bs[C] += bi[X][Y];
			mis[C] = -1;
		}
	}
	if(mis[C] == -1) {
		uni[A][B] = us[C] - uni[A][B^1] + 1;
		bi[A][B] = mnst(A, B) + mnst(A, B) * mnst(A, B^1) * (bs[C] - bi[A][B^1]);
	}
	else {
		uni[A][B] = us[C] + 1;
		bi[A][B] = mnst(A, B) + mnst(A, B) * mnst(A, B^1) * bs[C];
	}
}

void solve (ll C, ll P) {
	ll A, B;
	tie(A, B) = conv(C, P);
	if(!mnst(A, B)) return;
	ans += uni[A][B] * (st[P] - uni[A][B] * (bs[P] - bi[A][B]) - bi[A][B] * (us[P] - uni[A][B]) + 2 * (bs[P] - bi[A][B]));
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=m;i++) {
		ll A, B;
		scanf("%lld%lld",&A,&B);
		raw[A].push_back(B);
		raw[B].push_back(A);
	}
	for(ll i=1;i<=n;i++) {
		if(!v2[i]) dfst(i, 0);
	}
	iota(p+1, p+1+n, 1);
	for(ll i=1;i<=n;i++) {
		if(par[i] == 0) continue;
		adj[par[i]].push_back(i);
		adj[i].push_back(par[i]);
	}
	for(ll i=1;i<=n;i++) for(auto &j : raw[i]) {
		if(dfn[i] < dfn[j] || par[i] == j) continue;
		while(true) {
			ll T = Find(i);
			if(dfn[par[T]] <= dfn[j]) break;
			p[T] = par[T];
		}
	}
	for(ll i=1;i<=n;i++) for(auto &j : adj[i]) {
		calc(i, j);
	}
	for(ll i=1;i<=n;i++) {
		us[i] = 0;
		bs[i] = 0;
		for(auto &j : adj[i]) {
			ll A, B;
			tie(A, B) = conv(j, i);
			us[i] += uni[A][B];
			bs[i] += bi[A][B];
			ans -= uni[A][B] * uni[A][B];
		}
		ans += us[i] * us[i];
		for(auto &j : adj[i]) {
			ll A, B;
			tie(A, B) = conv(j, i);
			if(!mnst(A, B)) {
				us[i] += uni[A][B];
				uni[A][B] *= 2;
			}
			st[i] -= uni[A][B] * bi[A][B];
		}
		st[i] += us[i] * bs[i];
	}
	for(ll i=1;i<=n;i++) for(auto &j : adj[i]) {
		solve(i, j);
	}
	printf("%lld\n",ans);
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~
count_triplets.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&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