oj.uz

Submission #745135

# Submission time Handle Problem Language Result Execution time Memory
745135 2023-05-19T12:31:08 Z b00norp Duathlon (APIO18_duathlon) C++14
66 / 100
 282 ms 36004 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

/*
- Make a bridge tree of the graph

- Store all the sizes of the nodes in bridge tree

- Case 1: 

All 3 nodes in the same node (all s, c, f)
(siz) * (siz - 1) * (siz - 2)

- Case 2: 2 nodes in the same node. 1 node away (s, c) or (c, f)
s / f cannot be the node that joins the bridge node and the away node
=> -1 candidate for f, same candidates for c
=> [[(component_siz - siz) * (siz - 1) * (siz - 1)]] * 2 (for the 2 options)

- Case 3: 1 node here, 2 nodes in different subtrees (c)
=> if bridge is from same node, only that node can be c
=> else, siz options

*/

const int INF = 1e18;

const int N = 1e5 + 5;
bool vis[N]; // visited track
vector<int> g[N]; // graph
vector<array<int, 2> > bcc[N]; // bridge tree graph (to, connector)
int low[N], disc[N], tim = 1;
set<pair<int, int> > bridges;
int siz[N], component[N]; // size of bridge tree node i, component of node i of original graph
int subtree[N];
int tot_siz[N]; // total size of the bridge tree component
int ans = 0;

void dfs(int node, int par)
{
	low[node] = tim;
	disc[node] = tim++;
	vis[node] = true;
	for(int to: g[node])
	{
		if(to == par) continue;
		if(vis[to])
		{
			low[node] = min(low[node], disc[to]);
		}
		else
		{
			dfs(to, node);
			low[node] = min(low[node], low[to]);
			if(low[to] > disc[node])
			{
				bridges.insert({node, to});
				bridges.insert({to, node});
			}
		}
	}
}

void add_component(int node, int par, int comp)
{
	siz[comp] += 1;
	component[node] = comp;
	vis[node] = true;
	for(int to: g[node])
	{
		if(vis[to]) continue;
		if(bridges.count({node, to}))
		{
			continue;
		}
		add_component(to, node, comp);
	}
}

int FindSiz(int node)
{
	subtree[node] = siz[node];
	int ans = siz[node];
	vis[node] = true;
	for(auto [to, temp]: bcc[node])
	{
		if(vis[to]) continue;
		ans += FindSiz(to);
		subtree[node] += subtree[to];
	}
	return ans;
}

void UpdateSiz(int node, int val)
{
	tot_siz[node] = val;
	for(auto [to, temp]: bcc[node])
	{
		if(tot_siz[to] != val)
		{
			UpdateSiz(to, val);
		}
	}
}

void Solve() 
{
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i = 1; i <= n; i++)
	{
		if(!vis[i])
		{
			dfs(i, -1);
		}
	}
	for(int i = 1; i <= n; i++)
	{
		vis[i] = false;
	}
	int cnt = 0;
	for(int i = 1; i <= n; i++)
	{
		if(!vis[i])
		{
			cnt += 1;
			add_component(i, -1, cnt);
		}
	}
	for(auto [u, v]: bridges)
	{
		bcc[component[u]].push_back({component[v], u});
	}

	// implementing case 1:
	for(int i = 1; i <= cnt; i++)
	{
		ans += siz[i] * (siz[i] - 1) * (siz[i] - 2);
	}
	// implementation ends

	for(int i = 1; i <= cnt; i++)
	{
		vis[i] = false;
	}
	for(int i = 1; i <= cnt; i++)
	{
		if(!vis[i])
		{
			int temp = FindSiz(i);
			UpdateSiz(i, temp);
		}
	}

	// implementing case 2:
	for(int i = 1; i <= cnt; i++)
	{
		ans += (tot_siz[i] - siz[i]) * (siz[i] - 1) * (siz[i] - 1) * 2LL;
	}
	// implementation ends

	// implementing case 3:
	// cout << "subtree\n";
	// for(int i = 1; i <= n; i++)
	// {
	// 	cout << subtree[i] << " ";
	// }
	// cout << "\n";
	for(int i = 1; i <= cnt; i++)
	{
		// cout << "tot_siz[i] = " << tot_siz[i] << ", siz[i] = " << siz[i] << "\n";
		// cout << "subtree[i] = " << subtree[i] << endl;
		map<int, int> mp;
		for(auto [to, connector]: bcc[i])
		{
			// cout << "to = " << to << ", connector = " << connector << "\n";
			mp[connector] += subtree[to];
			if(subtree[to] > subtree[i])
			{
				mp[connector] -= subtree[to];
				mp[connector] += (tot_siz[i] - subtree[i]);
			}
		}
		// for(auto i: mp)
		// {
		// 	cout << "connector: " << i.first << ", connector size = " << i.second << "\n";
		// }
		for(auto [to, connector]: bcc[i])
		{
			int going = subtree[to];
			if(subtree[to] > subtree[i])
			{
				going = tot_siz[i] - subtree[i];
			}
			int excluding_this = tot_siz[i] - siz[i] - mp[connector];
			// cout << "excluding_this = " << excluding_this << "\n";
			int cur_ans = 0;
			// cout << "siz[to] = " << going << ", left = " << mp[connector] - subtree[to] << "\n";
			// only one node usable
			cur_ans += (going * (mp[connector] - going));
			// all usable
			cur_ans += (going * siz[i] * excluding_this);
			ans += cur_ans;
			// cout << "ans = " << ans << "\n";
		}
	}
	cout << ans << "\n";
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    //cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message

count_triplets.cpp: In function 'long long int FindSiz(long long int)':
count_triplets.cpp:87:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |  for(auto [to, temp]: bcc[node])
      |           ^
count_triplets.cpp: In function 'void UpdateSiz(long long int, long long int)':
count_triplets.cpp:99:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |  for(auto [to, temp]: bcc[node])
      |           ^
count_triplets.cpp: In function 'void Solve()':
count_triplets.cpp:139:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  139 |  for(auto [u, v]: bridges)
      |           ^
count_triplets.cpp:183:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  183 |   for(auto [to, connector]: bcc[i])
      |            ^
count_triplets.cpp:197:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  197 |   for(auto [to, connector]: bcc[i])
      |            ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5004 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Incorrect 3 ms 4948 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5004 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Incorrect 3 ms 4948 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 21460 KB Output is correct
2 Correct 77 ms 21452 KB Output is correct
3 Correct 153 ms 25732 KB Output is correct
4 Correct 118 ms 24908 KB Output is correct
5 Correct 132 ms 22012 KB Output is correct
6 Correct 160 ms 26232 KB Output is correct
7 Correct 182 ms 25704 KB Output is correct
8 Correct 172 ms 26652 KB Output is correct
9 Correct 167 ms 24624 KB Output is correct
10 Correct 153 ms 23676 KB Output is correct
11 Correct 128 ms 19988 KB Output is correct
12 Correct 108 ms 19972 KB Output is correct
13 Correct 103 ms 19896 KB Output is correct
14 Correct 107 ms 19556 KB Output is correct
15 Correct 87 ms 18948 KB Output is correct
16 Correct 83 ms 18356 KB Output is correct
17 Correct 8 ms 9780 KB Output is correct
18 Correct 8 ms 9776 KB Output is correct
19 Correct 8 ms 9812 KB Output is correct
20 Correct 7 ms 9812 KB Output is correct
21 Correct 7 ms 9776 KB Output is correct
22 Correct 7 ms 9812 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 4 ms 5332 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 5 ms 5332 KB Output is correct
9 Correct 4 ms 5332 KB Output is correct
10 Correct 4 ms 5252 KB Output is correct
11 Correct 4 ms 5308 KB Output is correct
12 Correct 4 ms 5284 KB Output is correct
13 Correct 4 ms 5260 KB Output is correct
14 Correct 4 ms 5288 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Correct 4 ms 5332 KB Output is correct
18 Correct 4 ms 5332 KB Output is correct
19 Correct 4 ms 5332 KB Output is correct
20 Correct 3 ms 5332 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 31092 KB Output is correct
2 Correct 238 ms 31180 KB Output is correct
3 Correct 223 ms 31096 KB Output is correct
4 Correct 237 ms 31180 KB Output is correct
5 Correct 218 ms 31076 KB Output is correct
6 Correct 241 ms 36004 KB Output is correct
7 Correct 282 ms 34892 KB Output is correct
8 Correct 262 ms 33772 KB Output is correct
9 Correct 233 ms 32820 KB Output is correct
10 Correct 246 ms 31156 KB Output is correct
11 Correct 219 ms 31440 KB Output is correct
12 Correct 210 ms 31456 KB Output is correct
13 Correct 252 ms 31344 KB Output is correct
14 Correct 198 ms 29468 KB Output is correct
15 Correct 167 ms 27492 KB Output is correct
16 Correct 105 ms 21432 KB Output is correct
17 Correct 170 ms 31092 KB Output is correct
18 Correct 197 ms 31192 KB Output is correct
19 Correct 203 ms 31188 KB Output is correct
20 Correct 191 ms 31156 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5176 KB Output is correct
13 Correct 5 ms 5204 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Correct 4 ms 5204 KB Output is correct
18 Correct 3 ms 5176 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 3 ms 5076 KB Output is correct
21 Correct 4 ms 5204 KB Output is correct
22 Correct 4 ms 5176 KB Output is correct
23 Correct 3 ms 5204 KB Output is correct
24 Correct 3 ms 5204 KB Output is correct
25 Correct 3 ms 5036 KB Output is correct
26 Correct 3 ms 5076 KB Output is correct
27 Correct 3 ms 5076 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 31092 KB Output is correct
2 Correct 210 ms 30972 KB Output is correct
3 Correct 188 ms 26024 KB Output is correct
4 Correct 166 ms 20636 KB Output is correct
5 Correct 102 ms 16376 KB Output is correct
6 Correct 104 ms 14988 KB Output is correct
7 Correct 85 ms 14216 KB Output is correct
8 Correct 82 ms 13436 KB Output is correct
9 Correct 96 ms 12948 KB Output is correct
10 Correct 78 ms 12736 KB Output is correct
11 Correct 62 ms 12388 KB Output is correct
12 Correct 63 ms 12252 KB Output is correct
13 Correct 59 ms 12312 KB Output is correct
14 Correct 63 ms 14804 KB Output is correct
15 Correct 200 ms 30392 KB Output is correct
16 Correct 197 ms 28856 KB Output is correct
17 Correct 177 ms 26952 KB Output is correct
18 Correct 170 ms 25400 KB Output is correct
19 Correct 151 ms 20684 KB Output is correct
20 Correct 141 ms 20728 KB Output is correct
21 Correct 154 ms 20696 KB Output is correct
22 Correct 118 ms 18632 KB Output is correct
23 Correct 87 ms 16552 KB Output is correct
24 Correct 161 ms 25756 KB Output is correct
25 Correct 176 ms 25768 KB Output is correct
26 Correct 146 ms 22512 KB Output is correct
27 Correct 152 ms 22440 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5004 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Incorrect 3 ms 4948 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5004 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Incorrect 3 ms 4948 KB Output isn't correct
9 Halted 0 ms 0 KB -