oj.uz

Submission #381099

# Submission time Handle Problem Language Result Execution time Memory
381099 2021-03-24T13:32:16 Z Return_0 Duathlon (APIO18_duathlon) C++17
31 / 100
 147 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]) - (pr == 0)) * 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 6 ms 7404 KB Output is correct
4 Correct 7 ms 7404 KB Output is correct
5 Correct 6 ms 7404 KB Output is correct
6 Correct 6 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 6 ms 7404 KB Output is correct
4 Correct 7 ms 7404 KB Output is correct
5 Correct 6 ms 7404 KB Output is correct
6 Correct 6 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 106 ms 21608 KB Output is correct
2 Correct 86 ms 21608 KB Output is correct
3 Correct 110 ms 21612 KB Output is correct
4 Correct 102 ms 21348 KB Output is correct
5 Correct 106 ms 18416 KB Output is correct
6 Correct 112 ms 20752 KB Output is correct
7 Correct 121 ms 18924 KB Output is correct
8 Correct 122 ms 19308 KB Output is correct
9 Correct 113 ms 17260 KB Output is correct
10 Correct 102 ms 17260 KB Output is correct
11 Correct 88 ms 14700 KB Output is correct
12 Correct 87 ms 14572 KB Output is correct
13 Correct 78 ms 14700 KB Output is correct
14 Correct 76 ms 14444 KB Output is correct
15 Correct 62 ms 13800 KB Output is correct
16 Correct 62 ms 13544 KB Output is correct
17 Correct 10 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 8 ms 8944 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 6 ms 7532 KB Output is correct
6 Correct 7 ms 7532 KB Output is correct
7 Correct 7 ms 7532 KB Output is correct
8 Correct 6 ms 7532 KB Output is correct
9 Correct 6 ms 7660 KB Output is correct
10 Correct 6 ms 7532 KB Output is correct
11 Correct 6 ms 7532 KB Output is correct
12 Correct 7 ms 7532 KB Output is correct
13 Correct 9 ms 7532 KB Output is correct
14 Correct 6 ms 7532 KB Output is correct
15 Correct 7 ms 7532 KB Output is correct
16 Correct 6 ms 7404 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 107 ms 16492 KB Output is correct
2 Correct 105 ms 16620 KB Output is correct
3 Correct 111 ms 16620 KB Output is correct
4 Correct 117 ms 16620 KB Output is correct
5 Correct 147 ms 16492 KB Output is correct
6 Correct 145 ms 26728 KB Output is correct
7 Correct 136 ms 23048 KB Output is correct
8 Correct 138 ms 21356 KB Output is correct
9 Correct 125 ms 19820 KB Output is correct
10 Correct 115 ms 16492 KB Output is correct
11 Correct 117 ms 16492 KB Output is correct
12 Correct 120 ms 16748 KB Output is correct
13 Correct 109 ms 16492 KB Output is correct
14 Correct 100 ms 16364 KB Output is correct
15 Correct 87 ms 15852 KB Output is correct
16 Correct 58 ms 13928 KB Output is correct
17 Correct 63 ms 15588 KB Output is correct
18 Correct 66 ms 15588 KB Output is correct
19 Correct 71 ms 15712 KB Output is correct
20 Correct 95 ms 15596 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 6 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 113 ms 16620 KB Output is correct
2 Correct 142 ms 16876 KB Output is correct
3 Incorrect 110 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 6 ms 7404 KB Output is correct
4 Correct 7 ms 7404 KB Output is correct
5 Correct 6 ms 7404 KB Output is correct
6 Correct 6 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 6 ms 7404 KB Output is correct
4 Correct 7 ms 7404 KB Output is correct
5 Correct 6 ms 7404 KB Output is correct
6 Correct 6 ms 7404 KB Output is correct
7 Incorrect 6 ms 7404 KB Output isn't correct
8 Halted 0 ms 0 KB -