oj.uz

Submission #720834

# Submission time Handle Problem Language Result Execution time Memory
720834 2023-04-09T12:29:51 Z NothingXD Duathlon (APIO18_duathlon) C++17
31 / 100
 153 ms 18952 KB 
/*

   Wei Wai Wei Wai
   Zumigat nan damu dimi kwayt rayt

*/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
/*typedef __uint128_t L;
  struct FastMod {
  ull b, m;
  FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
  ull reduce(ull a) {
  ull q = (ull)((L(m) * a) >> 64);
  ull r = a - q * b; // can be proven that 0 <= r < 2*b
  return r >= b ? r - b : r;
  }
  };
  FastMod FM(2);
*/
void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 10;
const int inf = 1e9;

int n, m, par[maxn], a[maxn], cnt[maxn], sz[maxn], h[maxn];
vector<int> g[maxn], t[maxn];
bool vis[maxn], mark[maxn];
ll ans = 0;

int dfs(int v){
	vis[v] = true;
	int res = h[v], tmp = 0, cnt = (h[v] != 0);
	for (auto u: g[v]){
		if (!vis[u]){
			h[u] = h[v] + 1;
			int x = dfs(u);
			res = min(res, x);
			tmp = max(tmp, x);
			cnt++;
		}
		else res = min(res, h[u]);
	}
	if (cnt > 1 && tmp >= h[v]) mark[v] = true;
	return res;
}

int getpar(int v){
	return (par[v] == -1? v: par[v] = getpar(par[v]));
}

void merge(int u, int v){
	if ((u = getpar(u)) == (v = getpar(v))) return;
	par[v] = u;
}

void solve(int v, int p = -1){
	vis[v] = true;
	sz[v] = cnt[v];
	for (auto u: t[v]){
		if (u != p){
			solve(u, v);
			sz[v] += sz[u];
		}
	}
}

void Calc(int v, int r, int p = -1){
	ans += 1ll * (sz[r] - cnt[v]) * (sz[r] - cnt[v] - 1);
	if (mark[v]){
		for (auto u: g[v]){
			ans += 1ll * cnt[u] * (cnt[u] - 1);
			if (u != p) ans -= 1ll * sz[u] * (sz[u] - 1);
			else ans -= 1ll * (sz[r] - sz[v]) * (sz[r] - sz[v] - 1);
		}
	}
	else{
		ans += 1ll * cnt[v] * (cnt[v]-1) * (cnt[v]-2);
		for (auto u: g[v]){
			if (u != p){
				ans += 2ll * sz[u] * cnt[v] * (cnt[v]-1);
				ans -= 1ll * sz[u] * (sz[u] - 1);
			}
			else{
				ans += 2ll * (sz[r] - sz[v]) * cnt[v] * (cnt[v]-1);
				ans -= 1ll * (sz[r] - sz[v]) * (sz[r] - sz[v] - 1);
			}
		}
	}
	for (auto u: t[v]) if (u != p) Calc(u, r, v);
}


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

	memset(par, -1, sizeof par);
	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);
	for (int i = 1; i <= n; i++){
		for (auto u: g[i]){
			if (u > i && !mark[u] && !mark[i]) merge(i, u);
		}
	}

	for (int i = 1; i <= n; i++){
		a[i] = getpar(i);
		cnt[a[i]]++;
	}

	for (int i = 1; i <= n; i++){
		for (auto u: g[i]){
			if (u > i && (mark[u] || mark[i]) && getpar(u) != getpar(i)){
				t[a[u]].push_back(a[i]);
				t[a[i]].push_back(a[u]);
				merge(u, i);
			}
		}
	}

	memset(vis, false, sizeof vis);

	for (int i = 1; i <= n; i++){
		if (!vis[a[i]]){
			solve(a[i]);
			Calc(a[i], a[i]);
		}
	}

	cout << ans << '\n';

	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5460 KB Output is correct
2 Correct 3 ms 5472 KB Output is correct
3 Correct 4 ms 5424 KB Output is correct
4 Correct 3 ms 5460 KB Output is correct
5 Correct 3 ms 5424 KB Output is correct
6 Correct 3 ms 5460 KB Output is correct
7 Incorrect 4 ms 5428 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 77 ms 18480 KB Output is correct
2 Correct 64 ms 18424 KB Output is correct
3 Correct 86 ms 17008 KB Output is correct
4 Correct 81 ms 18060 KB Output is correct
5 Correct 92 ms 15140 KB Output is correct
6 Correct 109 ms 15876 KB Output is correct
7 Correct 84 ms 14920 KB Output is correct
8 Correct 87 ms 15512 KB Output is correct
9 Correct 79 ms 14100 KB Output is correct
10 Correct 101 ms 14540 KB Output is correct
11 Correct 62 ms 12724 KB Output is correct
12 Correct 59 ms 12572 KB Output is correct
13 Correct 59 ms 12240 KB Output is correct
14 Correct 55 ms 12112 KB Output is correct
15 Correct 45 ms 11096 KB Output is correct
16 Correct 50 ms 10984 KB Output is correct
17 Correct 6 ms 6996 KB Output is correct
18 Correct 6 ms 6996 KB Output is correct
19 Correct 7 ms 6868 KB Output is correct
20 Correct 6 ms 6868 KB Output is correct
21 Correct 6 ms 6868 KB Output is correct
22 Correct 6 ms 6868 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 14784 KB Output is correct
2 Correct 115 ms 14796 KB Output is correct
3 Correct 153 ms 14924 KB Output is correct
4 Correct 109 ms 14912 KB Output is correct
5 Correct 108 ms 14816 KB Output is correct
6 Correct 111 ms 18952 KB Output is correct
7 Correct 100 ms 17512 KB Output is correct
8 Correct 105 ms 16788 KB Output is correct
9 Correct 129 ms 16076 KB Output is correct
10 Correct 109 ms 14860 KB Output is correct
11 Correct 143 ms 14888 KB Output is correct
12 Correct 103 ms 14888 KB Output is correct
13 Correct 87 ms 14796 KB Output is correct
14 Correct 121 ms 14400 KB Output is correct
15 Correct 101 ms 13908 KB Output is correct
16 Correct 48 ms 11696 KB Output is correct
17 Correct 51 ms 15376 KB Output is correct
18 Correct 63 ms 15332 KB Output is correct
19 Correct 52 ms 15548 KB Output is correct
20 Correct 78 ms 15428 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 14880 KB Output is correct
2 Correct 97 ms 14788 KB Output is correct
3 Incorrect 118 ms 14576 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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