Submission #570601

#	Time	Username	Problem	Language	Result	Execution time	Memory
570601		keta_tsimakuridze	철인 이종 경기 (APIO18_duathlon)	C++14	31 / 100	254 ms	36040 KiB

count_triplets

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 2e5 + 5, mod = 1e9 + 7; //!
int t, h[N], vis[N], x[N], p[N], sz[N], ans, c[N], f[N];
vector<int> V[N], adj[N], v, X[N];
void dfs0(int u,int p) {
	h[u] = h[p] + 1; v.push_back(u);
	vis[u] = 1;
	for(int i = 0; i < V[u].size(); i++) {
		if(V[u][i] == p) continue;
		if(!vis[V[u][i]]) dfs0(V[u][i], u);
		else if(h[V[u][i]] < h[u]) x[u]++, x[V[u][i]]--;
	}
}
int find(int u) {
	return (p[u] == u ? p[u] : p[u] = find(p[u]));
}
void merge(int u,int v) {
	u = find(u), v = find(v);
	p[v] = u;
	sz[u] += sz[v];
	sz[v] = 0;
}
void dfs(int u,int p) {
	vis[u] = 1;
	for(int i = 0; i < V[u].size(); i++) {
		if(V[u][i] == p) continue;
		if(!vis[V[u][i]]) dfs(V[u][i], u), x[u] += x[V[u][i]];
	}
	if(x[u]) merge(p, u);
}
void dfs2(int u, int p) {
	vis[u] = 1;
	int xx = sz[u], P = -1;
	for(int i = 0; i < adj[u].size(); i++) {
		if(adj[u][i] == p) {
			P = X[u][i];
			continue;
		}
		dfs2(adj[u][i], u); 
		sz[u] += sz[adj[u][i]]; 
		c[X[u][i]] += sz[adj[u][i]];
		ans -= sz[adj[u][i]] * (sz[adj[u][i]] - 1) * xx;
		ans -= sz[adj[u][i]] * (xx - 1) * 2;
	}
	if(P != -1) c[P] += (v.size() - sz[u]);
	for(int i = 0; i < X[u].size(); i++) {
		if(!c[X[u][i]]) continue;
		int v = X[u][i];
		for(int j = 0; j < V[v].size(); j++) {
			if(find(V[v][j]) == u || f[find(V[v][j])] == v) continue;
			f[find(V[v][j])] = v;
			ans -= (xx - 1) * sz[find(V[v][j])] * (c[v] - sz[find(V[v][j])]);
		}
		
		c[v] = 0;
	}
	ans -= (v.size() - sz[u]) * (v.size() - sz[u] - 1) * xx;
	ans -= (v.size() - sz[u]) * (xx - 1) * 2;
}
main() {
//	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n, m;
	cin >> n >> m;
	for(int i = 2; i <= m + 1; i++) {
		int u, v;
		cin >> u >> v;
		V[u].push_back(v);
		V[v].push_back(u);
	}
	for(int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
	ans = 0;
	for(int i = 1; i <= n; i++) {
		v.clear();
		if(vis[i]) continue; 
		dfs0(i, 0); 
		for(int j = 0; j < v.size(); j++) vis[v[j]] = 0;
		dfs(i, 0);
		for(int j = 0; j < v.size(); j++) {
			int u = v[j];
			for(int k = 0; k < V[u].size(); k++) {
				if(find(V[u][k]) <= find(u)) continue;
				adj[find(u)].push_back(find(V[u][k]));
				X[find(u)].push_back(u);
				adj[find(V[u][k])].push_back(find(u));
				X[find(V[u][k])].push_back(V[u][k]);
			}
		}
		for(int j = 0; j < v.size(); j++) vis[v[j]] = 0;
		ans += (int)v.size() * ((int)v.size() - 1) * ((int)v.size() - 2);
		
		for(int j = 0; j < v.size();j++) { 
			if(v[j] == find(v[j]) && !vis[v[j]]) {
				dfs2(v[j], 0);
			}
		}
		for(int j = 0; j < v.size(); j++) vis[v[j]] = 1;
		
	}
	cout << ans;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs0(long long int, long long int)':
count_triplets.cpp:14:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs(long long int, long long int)':
count_triplets.cpp:31:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(long long int, long long int)':
count_triplets.cpp:40:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i = 0; i < adj[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~
count_triplets.cpp:52:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i = 0; i < X[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
count_triplets.cpp:55:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int j = 0; j < V[v].size(); j++) {
      |                  ~~^~~~~~~~~~~~~
count_triplets.cpp: At global scope:
count_triplets.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main() {
      | ^~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:82:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for(int j = 0; j < v.size(); j++) vis[v[j]] = 0;
      |                  ~~^~~~~~~~~~
count_triplets.cpp:84:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for(int j = 0; j < v.size(); j++) {
      |                  ~~^~~~~~~~~~
count_triplets.cpp:86:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |    for(int k = 0; k < V[u].size(); k++) {
      |                   ~~^~~~~~~~~~~~~
count_triplets.cpp:94:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for(int j = 0; j < v.size(); j++) vis[v[j]] = 0;
      |                  ~~^~~~~~~~~~
count_triplets.cpp:97:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for(int j = 0; j < v.size();j++) {
      |                  ~~^~~~~~~~~~
count_triplets.cpp:102:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for(int j = 0; j < v.size(); j++) vis[v[j]] = 1;
      |                  ~~^~~~~~~~~~

• 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