oj.uz

Submission #745049

# Submission time Handle Problem Language Result Execution time Memory
745049 2023-05-19T10:43:07 Z b00norp Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

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

const int INF = 1e18, N = 1e5 + 5;
vector<int> g[N];
int siz;
bool vis[N];
int subtree[N];
int ans = 0;
int n, m;

void dfsini(int node)
{
	vis[node] = true;
	subtree[node] = 1;
	siz++;
	for(int to: g[node])
	{
		if(vis[to]) continue;
		dfsini(to);
		subtree[node] += subtree[to];
	}
}

void dfs_calc(int node, int par = -1)
{
	ans += (siz - subtree[node]) * (subtree[node] - 1);
	for(int to: g[node])
	{
		if(to == par) continue;
		ans += (subtree[to]) * (siz - subtree[to] - 1);
	}

	for(int to: g[node])
	{
		if(to == par) continue;
		dfs_calc(to, node);
	}
}

void Solve() 
{
	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])
		{
			siz = 0;
			dfsini(i);
			dfs_calc(i);
		}
	}
	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;
}

/*
Sample 1:
4 3
1 2
2 3
3 4
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 506 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 506 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 449876 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2684 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2680 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 2 ms 2692 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 7168 KB Output is correct
2 Correct 44 ms 7236 KB Output is correct
3 Correct 43 ms 7192 KB Output is correct
4 Correct 40 ms 7272 KB Output is correct
5 Correct 41 ms 7184 KB Output is correct
6 Correct 80 ms 9960 KB Output is correct
7 Correct 51 ms 9384 KB Output is correct
8 Correct 47 ms 8884 KB Output is correct
9 Correct 49 ms 8296 KB Output is correct
10 Correct 42 ms 7280 KB Output is correct
11 Correct 44 ms 8468 KB Output is correct
12 Correct 43 ms 8488 KB Output is correct
13 Correct 42 ms 8448 KB Output is correct
14 Correct 40 ms 8064 KB Output is correct
15 Correct 37 ms 7752 KB Output is correct
16 Correct 21 ms 6600 KB Output is correct
17 Correct 28 ms 8720 KB Output is correct
18 Correct 29 ms 8680 KB Output is correct
19 Correct 30 ms 8684 KB Output is correct
20 Correct 36 ms 8688 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2736 KB Output is correct
3 Runtime error 667 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7256 KB Output is correct
2 Correct 47 ms 7096 KB Output is correct
3 Runtime error 760 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 506 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 506 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -