oj.uz

Submission #361303

# Submission time Handle Problem Language Result Execution time Memory
361303 2021-01-29T08:24:55 Z AmShZ Duathlon (APIO18_duathlon) C++11
23 / 100
 177 ms 33644 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], sum[xn];
pii E[xn];
ll ans;
vector <int> adj[xn], vec, mlf[xn];
vector <pip> G[xn];
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 id, int p = - 1){
	sz2[v] = sz[v];
	for (pip u : G[v]){
		if (u.A == p)
			continue;
		DFS2(u.A, s, u.B.B, v);
		sz2[v] += sz2[u.A];
		sum[u.B.A] += sz2[u.A];
		ans -= 1LL * sz2[u.A] * (sz2[u.A] - 1);
	}
	sum[id] += s - sz2[v];
	ans -= 1LL * (s - sz2[v]) * (s - sz2[v] - 1);
	for (int u : mlf[v])
		ans -= 1LL * sum[u] * (sum[u] + 1) * (sz[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 pv = E[i].A, pu = E[i].B;
		int v = get_root(pv);
		int u = get_root(pu);
		if (v == u)
			continue;
		G[v].push_back({u, {pv, pu}});
		G[u].push_back({v, {pu, pv}});
	}
	for (int i = 1; i <= n; ++ i)
		mlf[get_root(i)].push_back(i);
	for (int v : vec)
		ans += 1LL * sz2[v] * (sz2[v] - 1) * (sz2[v] - 2), DFS2(v, sz2[v], 0);
	cout << ans << endl;
			
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 29416 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 12 ms 14572 KB Output is correct
2 Correct 11 ms 14572 KB Output is correct
3 Correct 11 ms 14572 KB Output is correct
4 Correct 11 ms 14676 KB Output is correct
5 Correct 11 ms 14700 KB Output is correct
6 Correct 11 ms 14700 KB Output is correct
7 Correct 11 ms 14700 KB Output is correct
8 Correct 11 ms 14700 KB Output is correct
9 Correct 11 ms 14700 KB Output is correct
10 Correct 11 ms 14700 KB Output is correct
11 Correct 11 ms 14572 KB Output is correct
12 Correct 11 ms 14572 KB Output is correct
13 Correct 11 ms 14572 KB Output is correct
14 Correct 11 ms 14572 KB Output is correct
15 Correct 11 ms 14572 KB Output is correct
16 Correct 10 ms 14572 KB Output is correct
17 Correct 11 ms 14572 KB Output is correct
18 Correct 11 ms 14700 KB Output is correct
19 Correct 11 ms 14700 KB Output is correct
20 Correct 12 ms 14700 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 28908 KB Output is correct
2 Correct 130 ms 28972 KB Output is correct
3 Correct 144 ms 28844 KB Output is correct
4 Correct 141 ms 28848 KB Output is correct
5 Correct 132 ms 28908 KB Output is correct
6 Correct 149 ms 33644 KB Output is correct
7 Correct 156 ms 32492 KB Output is correct
8 Correct 177 ms 31468 KB Output is correct
9 Correct 139 ms 30444 KB Output is correct
10 Correct 136 ms 28976 KB Output is correct
11 Correct 144 ms 29036 KB Output is correct
12 Correct 149 ms 28908 KB Output is correct
13 Correct 127 ms 28908 KB Output is correct
14 Correct 130 ms 28524 KB Output is correct
15 Correct 114 ms 28012 KB Output is correct
16 Correct 80 ms 26092 KB Output is correct
17 Correct 86 ms 29276 KB Output is correct
18 Correct 91 ms 29268 KB Output is correct
19 Correct 106 ms 29448 KB Output is correct
20 Correct 85 ms 29276 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14572 KB Output is correct
2 Correct 11 ms 14572 KB Output is correct
3 Correct 13 ms 14572 KB Output is correct
4 Incorrect 11 ms 14572 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 29036 KB Output is correct
2 Correct 171 ms 28652 KB Output is correct
3 Correct 147 ms 26348 KB Output is correct
4 Incorrect 152 ms 25580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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