oj.uz

Submission #777876

# Submission time Handle Problem Language Result Execution time Memory
777876 2023-07-09T20:28:29 Z aryan12 Duathlon (APIO18_duathlon) C++17
66 / 100
 206 ms 37364 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;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5036 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 5036 KB Output is correct
7 Correct 2 ms 5044 KB Output is correct
8 Incorrect 2 ms 5040 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 5036 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 5036 KB Output is correct
7 Correct 2 ms 5044 KB Output is correct
8 Incorrect 2 ms 5040 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 47 ms 22700 KB Output is correct
2 Correct 41 ms 22732 KB Output is correct
3 Correct 110 ms 27000 KB Output is correct
4 Correct 74 ms 24872 KB Output is correct
5 Correct 100 ms 21964 KB Output is correct
6 Correct 120 ms 26220 KB Output is correct
7 Correct 104 ms 25648 KB Output is correct
8 Correct 144 ms 26660 KB Output is correct
9 Correct 103 ms 24688 KB Output is correct
10 Correct 93 ms 23708 KB Output is correct
11 Correct 73 ms 20020 KB Output is correct
12 Correct 71 ms 20024 KB Output is correct
13 Correct 99 ms 19868 KB Output is correct
14 Correct 66 ms 19532 KB Output is correct
15 Correct 58 ms 18948 KB Output is correct
16 Correct 58 ms 18324 KB Output is correct
17 Correct 7 ms 9872 KB Output is correct
18 Correct 6 ms 9776 KB Output is correct
19 Correct 6 ms 9812 KB Output is correct
20 Correct 6 ms 9812 KB Output is correct
21 Correct 6 ms 9812 KB Output is correct
22 Correct 6 ms 9812 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 32332 KB Output is correct
2 Correct 152 ms 32424 KB Output is correct
3 Correct 170 ms 32460 KB Output is correct
4 Correct 150 ms 32404 KB Output is correct
5 Correct 164 ms 32396 KB Output is correct
6 Correct 178 ms 37364 KB Output is correct
7 Correct 188 ms 36124 KB Output is correct
8 Correct 206 ms 35136 KB Output is correct
9 Correct 153 ms 34068 KB Output is correct
10 Correct 163 ms 32584 KB Output is correct
11 Correct 148 ms 32436 KB Output is correct
12 Correct 152 ms 32388 KB Output is correct
13 Correct 152 ms 32428 KB Output is correct
14 Correct 146 ms 30356 KB Output is correct
15 Correct 135 ms 28296 KB Output is correct
16 Correct 103 ms 21896 KB Output is correct
17 Correct 136 ms 32200 KB Output is correct
18 Correct 158 ms 32272 KB Output is correct
19 Correct 154 ms 32104 KB Output is correct
20 Correct 143 ms 32152 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5172 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 4 ms 5096 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5048 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 3 ms 5048 KB Output is correct
12 Correct 3 ms 5204 KB Output is correct
13 Correct 3 ms 5176 KB Output is correct
14 Correct 4 ms 5176 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Correct 3 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 3 ms 5204 KB Output is correct
22 Correct 3 ms 5204 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 5040 KB Output is correct
26 Correct 3 ms 5040 KB Output is correct
27 Correct 2 ms 5076 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 32352 KB Output is correct
2 Correct 171 ms 32240 KB Output is correct
3 Correct 125 ms 25956 KB Output is correct
4 Correct 95 ms 20636 KB Output is correct
5 Correct 71 ms 16384 KB Output is correct
6 Correct 62 ms 15024 KB Output is correct
7 Correct 74 ms 14196 KB Output is correct
8 Correct 79 ms 13368 KB Output is correct
9 Correct 57 ms 13020 KB Output is correct
10 Correct 47 ms 12732 KB Output is correct
11 Correct 47 ms 12388 KB Output is correct
12 Correct 38 ms 12228 KB Output is correct
13 Correct 44 ms 12356 KB Output is correct
14 Correct 38 ms 14800 KB Output is correct
15 Correct 180 ms 30376 KB Output is correct
16 Correct 169 ms 28876 KB Output is correct
17 Correct 137 ms 26976 KB Output is correct
18 Correct 129 ms 25384 KB Output is correct
19 Correct 97 ms 20752 KB Output is correct
20 Correct 90 ms 20664 KB Output is correct
21 Correct 90 ms 20656 KB Output is correct
22 Correct 100 ms 18652 KB Output is correct
23 Correct 72 ms 16540 KB Output is correct
24 Correct 129 ms 25696 KB Output is correct
25 Correct 117 ms 25832 KB Output is correct
26 Correct 94 ms 22468 KB Output is correct
27 Correct 127 ms 22476 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 5036 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 5036 KB Output is correct
7 Correct 2 ms 5044 KB Output is correct
8 Incorrect 2 ms 5040 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 5036 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 2 ms 5036 KB Output is correct
7 Correct 2 ms 5044 KB Output is correct
8 Incorrect 2 ms 5040 KB Output isn't correct
9 Halted 0 ms 0 KB -