Submission #361307

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
361307	2021-01-29T08:36:58 Z	AmShZ	Duathlon (APIO18_duathlon)	C++11	66 / 100	158 ms	33388 KB

count_triplets

//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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-

Submission #361307

Compilation message