oj.uz

Submission #361288

# Submission time Handle Problem Language Result Execution time Memory
361288 2021-01-29T07:38:06 Z AmShZ Duathlon (APIO18_duathlon) C++11
23 / 100
 141 ms 24172 KB 
//khodaya khodet komak kon
# include <bits/stdc++.h>
 
/*
// ordered_set 
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
# define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
 
using namespace std;
 
typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;
 
# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define InTheNameOfGod                                  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
 
const int xn = 2e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod = 998244353;
const int base = 257;

int n, m, sz[xn], par[xn], P[xn], H[xn];
int f[xn], sz2[xn];
pii E[xn];
ll ans;
vector <int> adj[xn], G[xn], vec;
bool mark[xn];

int get_root(int v){
	if (v == P[v])
		return v;
	return P[v] = get_root(P[v]);
}
void merge(int v, int u){
	v = get_root(v);
	u = get_root(u);
	if (v == u)
		return;
	if (sz[v] < sz[u])
		swap(v, u);
	P[u] = v;
	sz[v] += sz[u];
	if (H[f[u]] < H[f[v]])
		f[v] = f[u];
}

void DFS(int v){
	mark[v] = true;
	sz2[v] = 1;
	for (int u : adj[v]){
		if (mark[u]){
			if (H[u] >= H[v] || u == par[v])
				continue;
			int res = v;
			while (get_root(res) != get_root(u)){
				res = get_root(res);
				merge(f[res], par[f[res]]);
			}
			continue;
		}
		H[u] = H[v] + 1;
		par[u] = v;
		DFS(u);
		sz2[v] += sz2[u];
	}
}
void DFS2(int v, int s, int p = - 1){
	sz2[v] = sz[v];
	for (int u : G[v]){
		if (u == p)
			continue;
		DFS2(u, s, v);
		sz2[v] += sz2[u];
		ans -= 1LL * (sz[v] - 1) * (sz2[u]) * (sz2[u] + 1) + 1LL * sz2[u] * (sz2[u] - 1);
	}
	ans -= 1LL * (s - sz2[v]) * (s - sz2[v] + 1) * (sz[v] - 1) + 1LL * (s - sz2[v]) * (s - sz2[v] - 1);
}

int main(){
	InTheNameOfGod;
	
	cin >> n >> m;
	for (int i = 0; i < m; ++ i){
		int v, u;
		cin >> v >> u;
		adj[v].push_back(u);
		adj[u].push_back(v);
		E[i] = {v, u};
	}
	for (int i = 1; i <= n; ++ i){
		P[i] = f[i] = i;
		sz[i] = 1;
	}
	for (int i = 1; i <= n; ++ i){
		if (mark[i])
			continue;
		DFS(i);
		vec.push_back(i);
	}
	for (int i = 0; i < m; ++ i){
		int v = E[i].A, u = E[i].B;
		v = get_root(v);
		u = get_root(u);
		if (v == u)
			continue;
		G[v].push_back(u);
		G[u].push_back(v);
	}
	for (int v : vec)
		ans += 1LL * sz2[v] * (sz2[v] - 1) * (sz2[v] - 2), DFS2(v, sz2[v]);
	cout << ans << endl;
			
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 19692 KB Output is correct
2 Correct 102 ms 19692 KB Output is correct
3 Correct 103 ms 19692 KB Output is correct
4 Correct 97 ms 19692 KB Output is correct
5 Correct 125 ms 19820 KB Output is correct
6 Correct 117 ms 23768 KB Output is correct
7 Correct 141 ms 22456 KB Output is correct
8 Correct 129 ms 21632 KB Output is correct
9 Correct 121 ms 21100 KB Output is correct
10 Correct 115 ms 19692 KB Output is correct
11 Correct 101 ms 20716 KB Output is correct
12 Correct 98 ms 20716 KB Output is correct
13 Correct 114 ms 20844 KB Output is correct
14 Correct 91 ms 20460 KB Output is correct
15 Correct 89 ms 20204 KB Output is correct
16 Correct 62 ms 18156 KB Output is correct
17 Correct 64 ms 21348 KB Output is correct
18 Correct 72 ms 21348 KB Output is correct
19 Correct 68 ms 21600 KB Output is correct
20 Correct 71 ms 21356 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9836 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Incorrect 7 ms 9836 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 19692 KB Output is correct
2 Correct 113 ms 19692 KB Output is correct
3 Incorrect 104 ms 18668 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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