oj.uz

Submission #358226

# Submission time Handle Problem Language Result Execution time Memory
358226 2021-01-25T08:43:04 Z shivensinha4 Duathlon (APIO18_duathlon) C++17
10 / 100
 1000 ms 1048580 KB 
#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXN = 1e5;
vi adj[MXN], apAdj[MXN];
int low[MXN], tin[MXN], sz[MXN], initSz[MXN], apComp[MXN];
bool ap[MXN], vis[MXN], seen[MXN];
vector<vi> comp;
int pt = 0, m;
ll rem = 0, n;

void dfs(int p, int parent) {
	comp[comp.size()-1].push_back(p);
	vis[p] = true;
	low[p] = tin[p] = pt++;
	bool seenChild = false;
	for (auto &i: adj[p]) if (i != parent) {
		if (vis[i]) {
			low[p] = min(low[p], tin[i]);
			continue;
		}
		
		dfs(i, p);
		
		if (seenChild and parent == p) ap[p] = true;
		else seenChild = true;
		
		low[p] = min(low[p], low[i]);
		if (low[i] >= tin[p] and parent != p) ap[p] = true;
		
		low[p] = min(low[p], low[i]);
	}
}

void findSz(int p, int parent) {
	sz[p] = initSz[p];
	for (auto &i: apAdj[p]) if (i != parent) {
		findSz(i, p);
		sz[p] += sz[i];
	}
}

void reroot(int p, int parent) {
	for (auto &i: apAdj[p]) {
		rem += sz[i] * (sz[i]-1) + (initSz[p]-1) * sz[i] * (sz[i]+1);
		if (i != parent) {
			sz[p] -= sz[i];
			sz[i] += sz[p];
			reroot(i, p);
			sz[i] -= sz[p];
			sz[p] += sz[i];
		}
	}
}


int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	for_(i, 0, m) {
		int a, b; cin >> a >> b;
		a -= 1; b -= 1;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	
	for_(i, 0, n) if (!vis[i]) {
		comp.push_back({});
		dfs(i, i);
	}
	
	for_(i, 0, n) if (adj[i].size() == 1) ap[i] = true;
	
	ll tot = 0;
	for (auto &c: comp) {
		vi apList;
		ll v = c.size();
		tot += v * (v-1) * (v-2);
		for (int &i: c) if (ap[i]) apList.push_back(i);
		if (!apList.size()) continue;
		
		queue<int> q;
		q.push(apList[0]);
		seen[apList[0]] = true;
		while (q.size()) {
			int p = q.front(); q.pop();
			apComp[p] = p;
			initSz[p]++;
			for (auto &i: adj[p]) {
				if (ap[i]) {
					apAdj[p].push_back(i);
					if (!seen[i]) {
						seen[i] = true;
						q.push(i);
					}
				}
				else {
					initSz[p]++;
					apComp[i] = p;
				}
			}
		}
		
		findSz(apList[0], apList[0]);
		reroot(apList[0], apList[0]);
	}
	
	cout << tot - rem << endl;
	
	
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Runtime error 664 ms 1048580 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Runtime error 664 ms 1048580 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 17528 KB Output is correct
2 Correct 84 ms 17392 KB Output is correct
3 Incorrect 109 ms 16496 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 14568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5228 KB Output is correct
2 Correct 5 ms 5228 KB Output is correct
3 Execution timed out 1133 ms 709096 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 14548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Runtime error 664 ms 1048580 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Runtime error 664 ms 1048580 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -