제출 #252443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
252443		amoo_safar	철인 이종 경기 (APIO18_duathlon)	C++14	0 / 100	409 ms	226796 KiB

count_triplets

#include<bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define debug(x) cerr << #x << " = " << x << '\n'

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 10;
const int N2 = N * 8;

ll ans;
int n, m;

int la;
vector<int> H[N], G[N2], R[N2];

int mk[N2], st[N], T = 1, dep[N2], wh[N];

void AddEdge(int u, int v){
	G[u].pb(v);
	G[v].pb(u);
	//cerr << u << ' ' << v << '\n';
}

int dfs(int u, int p, int d){
	mk[u] = 1;
	dep[u] = d;
	st[u] = T ++;

	int hbk = d, res;
	int cnt = (p == -1 ? 0 : 1);
	
	vector<pii> V;

	for(auto adj : H[u]){
		if(adj == p) continue;
		if(mk[adj]){
			hbk = min(hbk, dep[adj]);
		} else {
			res = dfs(adj, u, d + 1);
			hbk = min(hbk, res);
			if(res >= d){
				cnt ++;
				V.pb({T, cnt});
			} else {
				V.pb({T, 1});
			}

		}
	}
	//cerr << "! " << u << ' ' << cnt << ' ' << la << '\n';
	if(cnt > 0){
		wh[u] = la + 1;
		for(int i = 1; i <= cnt; i++) AddEdge(u, la + i);
		int idx;
		for(auto adj : H[u]){
			if(dep[adj] < dep[u]) idx = 1;
			else idx = upper_bound(V.begin(), V.end(), pii(st[adj], cnt + 1)) -> S;
			if(dep[adj] >= dep[u]) AddEdge(wh[adj], la + idx);
		}
		la += cnt;
	} else {
		assert(0);
	}
	return hbk;
}

int par[N2], sz[N];
int Find(int u){
	if(par[u] == u) return u;
	return par[u] = Find(par[u]);
}
void Unite(int u, int v){
	u = Find(u); v = Find(v);
	if(u == v) return ;
	par[u] = v;
	sz[v] += sz[u];
}

vector<pii> cut;
int DFS(int u, int p, int d){
	mk[u] = 1;
	dep[u] = d;

	int hbk = d, res;
	for(auto adj : G[u]){
		if(adj == p) continue;
		if(mk[adj]){
			hbk = min(hbk, dep[adj]);
			Unite(u, adj);
		} else {
			res = DFS(adj, u, d + 1);
			hbk = min(res, hbk);
			if(res <= d) Unite(adj, u);
			else {
				cut.pb(pii(adj, u));
			}
		}
	}
	return hbk;
}
int sub[N2];
vector<int> vis;
vector<pii> oth;
void DFS2(int u, int p, int d){
	vis.pb(u);
	sub[u] = sz[u];
	dep[u] = d;
	mk[u] = 1;
	for(auto adj : R[u]){
		if(adj == p) continue;
		DFS2(adj, u, d + 1);
		sub[u] += sub[adj];
	}
}

vector<int> com[N2];
vector<int> fuck[N2];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	int u, v;
	for(int i = 1; i <= m; i++){
		cin >> u >> v;
		H[u].pb(v);
		H[v].pb(u);
	}

	cerr << '\n';
	
	la = n;
	for(int i = 1; i <= n; i++){
		if(mk[i]) continue;
		dfs(i, -1, 0);
	}
	iota(par, par + N2, 0);
	fill(sz + 1, sz + n + 1, 1);

	memset(mk, 0, sizeof mk);
	for(int i = 1; i <= la; i++){
		if(mk[i]) continue;
		DFS(i, -1, 0);
	}
	for(int i = 1; i <= la; i++) com[Find(i)].pb(i);

	for(auto &x : cut){
		x.F = Find(x.F); x.S = Find(x.S);
		R[x.F].pb(x.S);
		R[x.S].pb(x.F);
	}

	memset(mk, 0, sizeof mk);
	
	for(int i = 1; i <= la; i++){
		if(mk[i]) continue;
		if(Find(i) != i) continue;
		vis.clear();
		DFS2(i, -1, 0);


		int sm = sub[i];
		for(auto nd : vis){
			oth.clear();
			vector<int> con;
			for(auto nd2 : com[nd]){
				int res = (nd2 <= n), res2 = 0, tmp;
				
				vector<pii> ed;
				for(auto adj : G[nd2]){
					if(Find(adj) == nd) continue;
					int tm;
					tmp = Find(adj);
					if(dep[tmp] > dep[nd]) tm = sub[tmp];
					else tm = sm - sub[nd];
					ed.pb({tm, adj});
					res += tm;
					res2 += tm;
				}
				ll S2 = 0;
				for(auto [tm, adj] : ed) S2 += (tm) * (tm - 1); 
				bool fl = false;
				for(auto [tm, adj] : ed){
					if((adj <= n) && (wh[adj] != adj)){
						fuck[adj].pb(sm - tm);
						//if(nd2 <= n) tm --;
						ans += 1ll * (res2 - tm) * (res2 - tm - 1);
						ans -= S2 - (tm * (tm - 1));

						ans += 2ll * (sm - res) * (res2 - tm);
						fl = true;
					}
				}
				oth.pb({res, fl});
			}
			ll Sum = 0, S2 = 0;
			for(auto [res, fl] : oth){
				Sum += res;
				S2 += res * (res - 1);
			}
			for(auto [res, fl] : oth){
				if(fl){
					ans += 1ll * (Sum - res) * (Sum - res - 1);
					ans -= S2 - (1ll * (res) * (res - 1));
				}
			}
				
		}
	}
	ans = 0;
	for(int i = 1; i <= n; i++){
		if(wh[i] == i) continue;

		int sm = 0;
		for(auto x : fuck[i]){
			sm += x;
			ans -= 1ll * x * (x - 1);
		}
		ans += 1ll * sm * (sm - 1);
	}
	cout << ans << '\n';
	return 0;
}
/*
9 10
1 2
2 3
3 4
4 5
4 2
3 6
6 7
6 8
8 3
8 9


10 9
1 2
2 3
*/

컴파일 시 표준 에러 (stderr) 메시지

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:186:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [tm, adj] : ed) S2 += (tm) * (tm - 1); 
              ^
count_triplets.cpp:186:22: warning: unused variable 'adj' [-Wunused-variable]
     for(auto [tm, adj] : ed) S2 += (tm) * (tm - 1); 
                      ^
count_triplets.cpp:188:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [tm, adj] : ed){
              ^
count_triplets.cpp:202:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for(auto [res, fl] : oth){
             ^
count_triplets.cpp:202:21: warning: unused variable 'fl' [-Wunused-variable]
    for(auto [res, fl] : oth){
                     ^
count_triplets.cpp:206:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for(auto [res, fl] : oth){
             ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10