Submission #172217

#	Time	Username	Problem	Language	Result	Execution time	Memory
172217		dndhk	Duathlon (APIO18_duathlon)	C++14	100 / 100	327 ms	36644 KiB

count_triplets

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 100000;

int N, M, NN;
vector<int> gp[MAX_N+1];
int dfsn[MAX_N+1], up[MAX_N+1], p[MAX_N+1], cnt, pcnt=1;
int sz2[MAX_N+1];
int vstt[MAX_N+1];
vector<int> v;

void dfs(int x){
	v.pb(x);
	vstt[x] = 1;
	sz2[x] = 1;
	dfsn[x] = up[x] = ++cnt;
	for(int i : gp[x]){
		if(i==p[x])	continue;
		if(dfsn[i]==0){
			p[i] = x;
			dfs(i);
			sz2[x]+=sz2[i];
			up[x] = min(up[x], up[i]);
		}else{
			up[x] = min(up[x], dfsn[i]);
		}
	}
}

vector<int> BCC[MAX_N+1];
vector<int> cl[MAX_N+1];
vector<pii> sz[MAX_N+1];
bool vst[MAX_N+1];
int sz3[MAX_N+1];
vector<pii> sz4[MAX_N+1];

void color(int x, int y){
	if(y>0){
		BCC[y].pb(x);
		cl[x].pb(y);
	}
	vst[x] = true;
	bool tf = false;
	int sum = 0;
	for(int i : gp[x]){
		if(vst[i])	continue;
		if(dfsn[x]<=up[i]){
			tf = true;
			BCC[++cnt].pb(x);
			if(N-sz2[i]-1!=0)	{
				sz[cnt].pb({x, N - sz2[i] - 1});
				sz4[x].pb({cnt, sz2[i]});
			}
			sum += sz2[i];
			cl[x].pb(cnt);
			color(i, cnt);
		}else{
			color(i, y);
		}
	}
	if(tf && y>0){
		sz[y].pb({x, sum});
		sz4[x].pb({y, N - 1 - sum});
	}
}

ll ans;


int main(){
	scanf("%d%d", &NN, &M);
	for(int i=1; i<=M; i++){
		int a, b; scanf("%d%d", &a, &b);
		gp[a].pb(b); gp[b].pb(a);
	}
	for(int i=1; i<=NN; i++){
		if(vstt[i]) continue;
		while(!v.empty())	v.pop_back();
		dfs(i); 
		N = v.size();
		cnt = pcnt-1; color(i, 0);
		ans += (ll)N * (ll)(N-1) * (ll)(N-2);
		for(int i:v){
			for(int j : cl[i]){
				sz3[i] += (BCC[j].size() - 1);
			}
		}
		for(int i=pcnt; i<=cnt; i++){
			ll sum1 = 0, sum2 = 0;
			ll num = 0;
			for(int j : BCC[i]){
				//TEST cout<<j<<" ";
				if(cl[j].size()==1)	num++;
			}
		//	TEST cout<<i<<endl;
			for(pii j : sz[i]){
				ans -= (ll)(BCC[i].size()-1) * (ll)(j.second+1) * (ll)(j.second);
				//TEST cout<<j.first<<" "<<(ll)(BCC[i].size()-1) * (ll)(j.second+1) * (ll)(j.second)<<endl;
			}/*
			// type 2
			
			TEST cout<<endl;
			TEST cout<<num<<endl;
			ans += num * (num-1LL) * (ll)(N - BCC[i].size()) * 2LL;
			for(pii j : sz[i]){
				sum2 += sum1 * (ll)j.second;
				sum1 += (ll)j.second;
				ans += 2LL * (ll)(BCC[i].size() - num - 1) * (ll)(N - j.second - sz3[j.first] - 1);
				ans += 2LL * num * (ll)(N - BCC[i].size() - j.second);
				// TEST cout<<j.first<<" "<<j.second<<endl;
				// TEST cout<<"*"<<(N-BCC[i].size() -j.second)<<endl;
				ans += 2LL * num * (ll)(N - sz3[j.first] - 1);
				// TEST cout<<"&"<<(j.second - sz3[j.first] + BCC[i].size() - 1)<<endl;
			}
			TEST cout<<num<<" "<<sum2<<endl;
			ans += num * 2LL * sum2;
			*/
		}
		/*TEST cout<<ans<<endl;
		for(int i : v){
			if(cl[i].size()>1){
				ll sum1 = 0, sum2 = 0;
				TEST cout<<i<<endl;
				for(pii j : sz4[i]){
					TEST cout<<j.first<<" "<<j.second<<endl;
					sum2 += (ll)(j.second - BCC[j.first].size() + 1) * sum1;
					sum1 += (ll)(j.second - BCC[j.first].size() + 1);
				}
				ans += 2LL * sum2;
			}
		}*/
		pcnt = cnt+1;
		cnt = 0;
	}
	cout<<ans<<endl;
	return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:111:7: warning: unused variable 'sum1' [-Wunused-variable]
    ll sum1 = 0, sum2 = 0;
       ^~~~
count_triplets.cpp:111:17: warning: unused variable 'sum2' [-Wunused-variable]
    ll sum1 = 0, sum2 = 0;
                 ^~~~
count_triplets.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &NN, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:95: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