oj.uz

답안 #361307

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
361307 2021-01-29T08:36:58 Z AmShZ 철인 이종 경기 (APIO18_duathlon) C++11
66 / 100
 158 ms 33388 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(get_root(v), sz2[v], 0);
	cout << ans << endl;
			
	return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 11 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 11 ms 14444 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Incorrect 10 ms 14444 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 11 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 11 ms 14444 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Incorrect 10 ms 14444 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 29288 KB Output is correct
2 Correct 101 ms 29780 KB Output is correct
3 Correct 117 ms 29544 KB Output is correct
4 Correct 105 ms 30436 KB Output is correct
5 Correct 124 ms 27748 KB Output is correct
6 Correct 137 ms 29800 KB Output is correct
7 Correct 118 ms 28652 KB Output is correct
8 Correct 142 ms 28908 KB Output is correct
9 Correct 136 ms 27500 KB Output is correct
10 Correct 119 ms 27372 KB Output is correct
11 Correct 121 ms 25964 KB Output is correct
12 Correct 111 ms 26112 KB Output is correct
13 Correct 102 ms 26088 KB Output is correct
14 Correct 94 ms 25832 KB Output is correct
15 Correct 78 ms 25704 KB Output is correct
16 Correct 89 ms 25448 KB Output is correct
17 Correct 21 ms 20588 KB Output is correct
18 Correct 21 ms 20716 KB Output is correct
19 Correct 21 ms 20588 KB Output is correct
20 Correct 21 ms 20588 KB Output is correct
21 Correct 21 ms 20456 KB Output is correct
22 Correct 21 ms 20456 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14572 KB Output is correct
2 Correct 11 ms 14572 KB Output is correct
3 Correct 10 ms 14572 KB Output is correct
4 Correct 10 ms 14700 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 10 ms 14700 KB Output is correct
9 Correct 10 ms 14700 KB Output is correct
10 Correct 11 ms 14572 KB Output is correct
11 Correct 11 ms 14572 KB Output is correct
12 Correct 10 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 11 ms 14720 KB Output is correct
17 Correct 11 ms 14592 KB Output is correct
18 Correct 10 ms 14572 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

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 28652 KB Output is correct
2 Correct 129 ms 28652 KB Output is correct
3 Correct 138 ms 28780 KB Output is correct
4 Correct 156 ms 28820 KB Output is correct
5 Correct 133 ms 28652 KB Output is correct
6 Correct 148 ms 33388 KB Output is correct
7 Correct 142 ms 32236 KB Output is correct
8 Correct 137 ms 31288 KB Output is correct
9 Correct 143 ms 30316 KB Output is correct
10 Correct 135 ms 28780 KB Output is correct
11 Correct 134 ms 28652 KB Output is correct
12 Correct 140 ms 28652 KB Output is correct
13 Correct 127 ms 28652 KB Output is correct
14 Correct 135 ms 28268 KB Output is correct
15 Correct 119 ms 27756 KB Output is correct
16 Correct 74 ms 25836 KB Output is correct
17 Correct 92 ms 29020 KB Output is correct
18 Correct 86 ms 29012 KB Output is correct
19 Correct 94 ms 29064 KB Output is correct
20 Correct 111 ms 29020 KB Output is correct

Subtask #6
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14572 KB Output is correct
2 Correct 10 ms 14572 KB Output is correct
3 Correct 10 ms 14572 KB Output is correct
4 Correct 10 ms 14572 KB Output is correct
5 Correct 11 ms 14572 KB Output is correct
6 Correct 11 ms 14572 KB Output is correct
7 Correct 11 ms 14572 KB Output is correct
8 Correct 11 ms 14572 KB Output is correct
9 Correct 11 ms 14572 KB Output is correct
10 Correct 11 ms 14572 KB Output is correct
11 Correct 13 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 14700 KB Output is correct
15 Correct 11 ms 14572 KB Output is correct
16 Correct 11 ms 14572 KB Output is correct
17 Correct 11 ms 14572 KB Output is correct
18 Correct 11 ms 14572 KB Output is correct
19 Correct 11 ms 14572 KB Output is correct
20 Correct 11 ms 14572 KB Output is correct
21 Correct 11 ms 14572 KB Output is correct
22 Correct 11 ms 14572 KB Output is correct
23 Correct 11 ms 14592 KB Output is correct
24 Correct 11 ms 14572 KB Output is correct
25 Correct 11 ms 14700 KB Output is correct
26 Correct 11 ms 14572 KB Output is correct
27 Correct 10 ms 14572 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 28652 KB Output is correct
2 Correct 142 ms 28396 KB Output is correct
3 Correct 148 ms 26188 KB Output is correct
4 Correct 122 ms 24428 KB Output is correct
5 Correct 119 ms 24812 KB Output is correct
6 Correct 104 ms 24172 KB Output is correct
7 Correct 114 ms 24044 KB Output is correct
8 Correct 97 ms 23788 KB Output is correct
9 Correct 102 ms 23660 KB Output is correct
10 Correct 89 ms 23532 KB Output is correct
11 Correct 89 ms 23404 KB Output is correct
12 Correct 99 ms 23404 KB Output is correct
13 Correct 95 ms 23404 KB Output is correct
14 Correct 90 ms 24940 KB Output is correct
15 Correct 158 ms 30864 KB Output is correct
16 Correct 144 ms 29804 KB Output is correct
17 Correct 146 ms 29164 KB Output is correct
18 Correct 133 ms 28484 KB Output is correct
19 Correct 122 ms 25964 KB Output is correct
20 Correct 140 ms 26192 KB Output is correct
21 Correct 119 ms 25964 KB Output is correct
22 Correct 120 ms 25452 KB Output is correct
23 Correct 113 ms 24940 KB Output is correct
24 Correct 112 ms 27748 KB Output is correct
25 Correct 121 ms 27816 KB Output is correct
26 Correct 151 ms 26656 KB Output is correct
27 Correct 133 ms 26824 KB Output is correct

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 11 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 11 ms 14444 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Incorrect 10 ms 14444 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 11 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 11 ms 14444 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Incorrect 10 ms 14444 KB Output isn't correct
9 Halted 0 ms 0 KB -