oj.uz

Submission #381098

# Submission time Handle Problem Language Result Execution time Memory
381098 2021-03-24T13:30:20 Z Return_0 Duathlon (APIO18_duathlon) C++17
31 / 100
 166 ms 26728 KB 
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef int ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< (x) << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A,class B> ostream& operator << (ostream& out,const pair<A,B>&a){return out<<'('<<a.first<<", "<<a.second<<')';}
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out<< '['; for (int i = -1; ++i < int(a.size());) out<< a[i] << (i + 1 < int(a.size()) ? ", " : ""); return out<<']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 1e5 + 7, M = 2e5 + 7;

ll h [N], sz [M], n, m, _n;
vector <ll> adj [N], adj2 [M], stk;
long long ans;

ll preDFS (ll v, ll pr) {
	_n++;
	ll low = h[v] = h[pr] + 1;
	stk.push_back(v);
	for (auto &u : adj[v]) {
		if (h[u]) low = min(low, h[u]);
		else low = min(low, preDFS(u, v));
	}
	if (low == h[pr]) {
		adj2[pr].push_back(n + v);
		for (; stk.back() != pr; stk.pop_back()) adj2[v + n].push_back(stk.back());
	}
	return low;
}

void dfs (ll v, ll pr) {
	sz[v] = v <= n;
	for (auto &u : adj2[v]) {
		dfs(u, v);
		sz[v] += sz[u];
		if (v > n) ans -= 1LL * SZ(adj2[v]) * sz[u] * (sz[u] - 1);
	}
	if (v > n) ans -= 1LL * SZ(adj2[v]) * (_n - sz[v]) * (_n - sz[v] - 1);
}

int main ()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>> n >> m;
	for (ll i = 0, v, u; i < m; i++) {
		cin>> v >> u;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}

	stk.push_back(0);
	for (ll i = 1; i <= n; i++) if (!h[i]) {
		_n = 0;
		preDFS(i, 0);
		ans += 1LL * _n * (_n - 1) * (_n - 2);
		dfs(i, 0);
	}

	cout<< ans << '\n';

	cerr<< "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

	return 0;
}
/*
4 3
1 2
2 3
3 4

4 4
1 2
2 3
3 4
2 4

*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 21608 KB Output is correct
2 Correct 82 ms 21608 KB Output is correct
3 Correct 119 ms 21712 KB Output is correct
4 Correct 111 ms 21348 KB Output is correct
5 Correct 113 ms 19476 KB Output is correct
6 Correct 118 ms 21868 KB Output is correct
7 Correct 114 ms 20076 KB Output is correct
8 Correct 129 ms 20332 KB Output is correct
9 Correct 123 ms 18284 KB Output is correct
10 Correct 130 ms 18412 KB Output is correct
11 Correct 101 ms 15724 KB Output is correct
12 Correct 90 ms 15596 KB Output is correct
13 Correct 84 ms 15596 KB Output is correct
14 Correct 87 ms 15340 KB Output is correct
15 Correct 87 ms 14440 KB Output is correct
16 Correct 67 ms 14440 KB Output is correct
17 Correct 9 ms 9076 KB Output is correct
18 Correct 9 ms 9076 KB Output is correct
19 Correct 9 ms 9076 KB Output is correct
20 Correct 9 ms 9076 KB Output is correct
21 Correct 9 ms 8944 KB Output is correct
22 Correct 9 ms 8944 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 16492 KB Output is correct
2 Correct 124 ms 16620 KB Output is correct
3 Correct 116 ms 16492 KB Output is correct
4 Correct 129 ms 16648 KB Output is correct
5 Correct 131 ms 16620 KB Output is correct
6 Correct 166 ms 26728 KB Output is correct
7 Correct 147 ms 23016 KB Output is correct
8 Correct 137 ms 21356 KB Output is correct
9 Correct 141 ms 19820 KB Output is correct
10 Correct 114 ms 16492 KB Output is correct
11 Correct 115 ms 17556 KB Output is correct
12 Correct 114 ms 17516 KB Output is correct
13 Correct 125 ms 17644 KB Output is correct
14 Correct 118 ms 17260 KB Output is correct
15 Correct 108 ms 16748 KB Output is correct
16 Correct 65 ms 14568 KB Output is correct
17 Correct 74 ms 16772 KB Output is correct
18 Correct 78 ms 16612 KB Output is correct
19 Correct 72 ms 16736 KB Output is correct
20 Correct 74 ms 16620 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 16632 KB Output is correct
2 Correct 133 ms 16876 KB Output is correct
3 Incorrect 127 ms 16108 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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