oj.uz

Submission #563092

# Submission time Handle Problem Language Result Execution time Memory
563092 2022-05-16T08:11:37 Z Bill_00 Duathlon (APIO18_duathlon) C++14
36 / 100
 925 ms 66900 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define N 1000000
#define INF 1000000007
#define ff first
#define ss second
typedef long long ll;
using namespace std;

bool vis[N], bridge[N], zam[100][100], cnt[15][15][15];
ll n, m, low[N], tin[N], h[N], sub[N], sz[N], timer, all, ans;
vector<pair<ll, ll> > adj[N];
vector<ll> adjt[N];

void dfs(ll node, ll par = 0){
	timer++;
	vis[node] = 1;
	tin[node] = timer;
	low[node] = tin[node];
	for(pair<ll, ll> child: adj[node]){
		ll to = child.ff;
		if(to == par) continue;
		if(vis[to] == 1){
			low[node] = min(low[node], tin[to]);
		}
		else{
			dfs(to, node);
			low[node] = min(low[node], low[to]);
			if(low[to] > tin[node]){
				bridge[child.ss] = 1;
			}
		}
	}
}

void dfs1(ll node, ll head){
	h[node] = head;
	vis[node] = 1;
	sz[head]++;
	for(pair<ll, ll> neigh : adj[node]){
		if(bridge[neigh.ss] == 1 && vis[neigh.ff] == 0){
			adjt[neigh.ff].push_back(head);
			adjt[head].push_back(neigh.ff);
			dfs1(neigh.ff, neigh.ff);
		}
		else{
			if(vis[neigh.ff] == 0){
				dfs1(neigh.ff, head);
			}
		}
	}
}
void dfs2(ll node, ll par = 0){
	// cout << node << ' ' << par << '\n';
	vis[node] = 1;
	sub[node] = sz[node];
	for(ll to : adjt[node]){
		if(to == par) continue;
		dfs2(to, node);
		sub[node] += sub[to];
	}
	// cout << sub[node] << ' ' << node << '\n';
}
void solve(ll node, ll par = 0){
	ll g = 0, h = 0;
	for(ll to : adjt[node]){
		if(to == par) continue;
		g += sub[to];
		h += (sub[to] * sub[to]);
	}
	ans += ((g * g - h + (all - sub[node]) * g * 2) * sz[node]);
	ans += (sz[node] * (sz[node] - 1) * (sz[node] - 2));
	ans += (2 * (sz[node] - 1) * (sz[node] - 1) * (all - sz[node]));
	for(ll to : adjt[node]){
		if(to == par) continue;
		solve(to, node);
	}
}

void subtask1(){
	int x[15];
	for(int i = 1; i <= n; i++) x[i] = i;
	do{
		int last = n;
		for(int i = 2; i <= n; i++){
			if(zam[x[i]][x[i - 1]] != 1){
				last = i - 1;
				break;
			}
		}
		for(int i = 1; i <= last; i++){
			for(int j = i + 1; j <= last; j++){
				for(int k = j + 1; k <= last; k++){
					if(cnt[x[i]][x[j]][x[k]] == 0){
						ans++;
						cnt[x[i]][x[j]][x[k]] = 1;
					}
				}
			}
		}
	}while(next_permutation(x + 1, x + n + 1));
	cout << ans;
}
int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	
    cin >> n >> m;
    for(ll i = 1; i <= m; i++){
    	ll x, y;
    	cin >> x >> y;
    	if(x <= 10 && y <= 10){
    		zam[x][y] = 1;
    		zam[y][x] = 1;
    	}
    	adj[x].push_back({y, i});
    	adj[y].push_back({x, i});
    }
    if(n <= 10){
    	subtask1();
    	return 0;
    }
    for(ll i = 1; i <= n; i++){
    	if(vis[i] == 0){
    		dfs(i);
    	}
    }
    memset(vis, 0, sizeof(vis));
    for(ll i = 1; i <= n; i++){
    	if(vis[i] == 0){
    		dfs1(i, i);
    	}
    }
    memset(vis, 0, sizeof(vis));
    for(ll i = 1; i <= n; i++){
    	if(vis[h[i]] == 0){
    		dfs2(h[i]);
    		all = sub[h[i]];
    		solve(h[i]);
    	}
    }
    cout << ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47216 KB Output is correct
2 Correct 26 ms 47192 KB Output is correct
3 Correct 26 ms 47188 KB Output is correct
4 Correct 26 ms 47180 KB Output is correct
5 Correct 29 ms 47220 KB Output is correct
6 Correct 55 ms 47288 KB Output is correct
7 Correct 57 ms 47188 KB Output is correct
8 Correct 65 ms 47216 KB Output is correct
9 Correct 117 ms 47284 KB Output is correct
10 Correct 925 ms 47288 KB Output is correct
11 Correct 60 ms 47188 KB Output is correct
12 Correct 60 ms 47332 KB Output is correct
13 Correct 56 ms 47284 KB Output is correct
14 Correct 57 ms 47188 KB Output is correct
15 Correct 56 ms 47288 KB Output is correct
16 Correct 59 ms 47208 KB Output is correct
17 Correct 58 ms 47284 KB Output is correct
18 Correct 55 ms 47188 KB Output is correct
19 Correct 55 ms 47296 KB Output is correct
20 Correct 55 ms 47284 KB Output is correct
21 Correct 54 ms 47284 KB Output is correct
22 Correct 56 ms 47296 KB Output is correct
23 Correct 29 ms 47188 KB Output is correct
24 Correct 27 ms 47252 KB Output is correct
25 Correct 30 ms 47188 KB Output is correct
26 Correct 58 ms 47240 KB Output is correct
27 Correct 28 ms 47188 KB Output is correct
28 Correct 29 ms 47188 KB Output is correct
29 Correct 54 ms 47200 KB Output is correct
30 Correct 28 ms 47188 KB Output is correct
31 Correct 33 ms 47296 KB Output is correct
32 Correct 60 ms 47284 KB Output is correct
33 Correct 29 ms 47180 KB Output is correct
34 Correct 31 ms 47248 KB Output is correct
35 Correct 55 ms 47224 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47216 KB Output is correct
2 Correct 26 ms 47192 KB Output is correct
3 Correct 26 ms 47188 KB Output is correct
4 Correct 26 ms 47180 KB Output is correct
5 Correct 29 ms 47220 KB Output is correct
6 Correct 55 ms 47288 KB Output is correct
7 Correct 57 ms 47188 KB Output is correct
8 Correct 65 ms 47216 KB Output is correct
9 Correct 117 ms 47284 KB Output is correct
10 Correct 925 ms 47288 KB Output is correct
11 Correct 60 ms 47188 KB Output is correct
12 Correct 60 ms 47332 KB Output is correct
13 Correct 56 ms 47284 KB Output is correct
14 Correct 57 ms 47188 KB Output is correct
15 Correct 56 ms 47288 KB Output is correct
16 Correct 59 ms 47208 KB Output is correct
17 Correct 58 ms 47284 KB Output is correct
18 Correct 55 ms 47188 KB Output is correct
19 Correct 55 ms 47296 KB Output is correct
20 Correct 55 ms 47284 KB Output is correct
21 Correct 54 ms 47284 KB Output is correct
22 Correct 56 ms 47296 KB Output is correct
23 Correct 29 ms 47188 KB Output is correct
24 Correct 27 ms 47252 KB Output is correct
25 Correct 30 ms 47188 KB Output is correct
26 Correct 58 ms 47240 KB Output is correct
27 Correct 28 ms 47188 KB Output is correct
28 Correct 29 ms 47188 KB Output is correct
29 Correct 54 ms 47200 KB Output is correct
30 Correct 28 ms 47188 KB Output is correct
31 Correct 33 ms 47296 KB Output is correct
32 Correct 60 ms 47284 KB Output is correct
33 Correct 29 ms 47180 KB Output is correct
34 Correct 31 ms 47248 KB Output is correct
35 Correct 55 ms 47224 KB Output is correct
36 Correct 27 ms 48304 KB Output is correct
37 Correct 27 ms 48212 KB Output is correct
38 Incorrect 26 ms 48232 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 66752 KB Output is correct
2 Correct 101 ms 66900 KB Output is correct
3 Correct 117 ms 64272 KB Output is correct
4 Correct 106 ms 66152 KB Output is correct
5 Correct 108 ms 61836 KB Output is correct
6 Correct 116 ms 62488 KB Output is correct
7 Correct 113 ms 61220 KB Output is correct
8 Correct 114 ms 62156 KB Output is correct
9 Correct 113 ms 60268 KB Output is correct
10 Correct 107 ms 60888 KB Output is correct
11 Correct 98 ms 58220 KB Output is correct
12 Correct 92 ms 57992 KB Output is correct
13 Correct 90 ms 57864 KB Output is correct
14 Correct 86 ms 57696 KB Output is correct
15 Correct 67 ms 57036 KB Output is correct
16 Correct 69 ms 56892 KB Output is correct
17 Correct 32 ms 52160 KB Output is correct
18 Correct 30 ms 52180 KB Output is correct
19 Correct 30 ms 52148 KB Output is correct
20 Correct 31 ms 52184 KB Output is correct
21 Correct 31 ms 52216 KB Output is correct
22 Correct 31 ms 52192 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 48340 KB Output is correct
2 Correct 27 ms 48392 KB Output is correct
3 Correct 26 ms 48448 KB Output is correct
4 Correct 27 ms 48456 KB Output is correct
5 Correct 31 ms 48488 KB Output is correct
6 Correct 28 ms 48364 KB Output is correct
7 Correct 28 ms 48468 KB Output is correct
8 Correct 27 ms 48456 KB Output is correct
9 Correct 27 ms 48468 KB Output is correct
10 Correct 28 ms 48336 KB Output is correct
11 Correct 28 ms 48332 KB Output is correct
12 Correct 27 ms 48424 KB Output is correct
13 Correct 27 ms 48448 KB Output is correct
14 Correct 28 ms 48520 KB Output is correct
15 Correct 28 ms 48368 KB Output is correct
16 Correct 28 ms 48348 KB Output is correct
17 Correct 28 ms 48352 KB Output is correct
18 Correct 27 ms 48336 KB Output is correct
19 Correct 27 ms 48340 KB Output is correct
20 Correct 27 ms 48344 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 61120 KB Output is correct
2 Correct 118 ms 61188 KB Output is correct
3 Correct 136 ms 61100 KB Output is correct
4 Correct 115 ms 61132 KB Output is correct
5 Correct 109 ms 61172 KB Output is correct
6 Correct 126 ms 66324 KB Output is correct
7 Correct 130 ms 64888 KB Output is correct
8 Correct 125 ms 63860 KB Output is correct
9 Correct 124 ms 62896 KB Output is correct
10 Correct 107 ms 61104 KB Output is correct
11 Correct 104 ms 61184 KB Output is correct
12 Correct 118 ms 61132 KB Output is correct
13 Correct 107 ms 61064 KB Output is correct
14 Correct 101 ms 60488 KB Output is correct
15 Correct 89 ms 59732 KB Output is correct
16 Correct 68 ms 57372 KB Output is correct
17 Correct 85 ms 60944 KB Output is correct
18 Correct 77 ms 60992 KB Output is correct
19 Correct 79 ms 61268 KB Output is correct
20 Correct 86 ms 60912 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 48340 KB Output is correct
2 Correct 27 ms 48356 KB Output is correct
3 Incorrect 29 ms 48340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 61132 KB Output is correct
2 Correct 118 ms 60912 KB Output is correct
3 Incorrect 120 ms 60548 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47216 KB Output is correct
2 Correct 26 ms 47192 KB Output is correct
3 Correct 26 ms 47188 KB Output is correct
4 Correct 26 ms 47180 KB Output is correct
5 Correct 29 ms 47220 KB Output is correct
6 Correct 55 ms 47288 KB Output is correct
7 Correct 57 ms 47188 KB Output is correct
8 Correct 65 ms 47216 KB Output is correct
9 Correct 117 ms 47284 KB Output is correct
10 Correct 925 ms 47288 KB Output is correct
11 Correct 60 ms 47188 KB Output is correct
12 Correct 60 ms 47332 KB Output is correct
13 Correct 56 ms 47284 KB Output is correct
14 Correct 57 ms 47188 KB Output is correct
15 Correct 56 ms 47288 KB Output is correct
16 Correct 59 ms 47208 KB Output is correct
17 Correct 58 ms 47284 KB Output is correct
18 Correct 55 ms 47188 KB Output is correct
19 Correct 55 ms 47296 KB Output is correct
20 Correct 55 ms 47284 KB Output is correct
21 Correct 54 ms 47284 KB Output is correct
22 Correct 56 ms 47296 KB Output is correct
23 Correct 29 ms 47188 KB Output is correct
24 Correct 27 ms 47252 KB Output is correct
25 Correct 30 ms 47188 KB Output is correct
26 Correct 58 ms 47240 KB Output is correct
27 Correct 28 ms 47188 KB Output is correct
28 Correct 29 ms 47188 KB Output is correct
29 Correct 54 ms 47200 KB Output is correct
30 Correct 28 ms 47188 KB Output is correct
31 Correct 33 ms 47296 KB Output is correct
32 Correct 60 ms 47284 KB Output is correct
33 Correct 29 ms 47180 KB Output is correct
34 Correct 31 ms 47248 KB Output is correct
35 Correct 55 ms 47224 KB Output is correct
36 Correct 27 ms 48304 KB Output is correct
37 Correct 27 ms 48212 KB Output is correct
38 Incorrect 26 ms 48232 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47216 KB Output is correct
2 Correct 26 ms 47192 KB Output is correct
3 Correct 26 ms 47188 KB Output is correct
4 Correct 26 ms 47180 KB Output is correct
5 Correct 29 ms 47220 KB Output is correct
6 Correct 55 ms 47288 KB Output is correct
7 Correct 57 ms 47188 KB Output is correct
8 Correct 65 ms 47216 KB Output is correct
9 Correct 117 ms 47284 KB Output is correct
10 Correct 925 ms 47288 KB Output is correct
11 Correct 60 ms 47188 KB Output is correct
12 Correct 60 ms 47332 KB Output is correct
13 Correct 56 ms 47284 KB Output is correct
14 Correct 57 ms 47188 KB Output is correct
15 Correct 56 ms 47288 KB Output is correct
16 Correct 59 ms 47208 KB Output is correct
17 Correct 58 ms 47284 KB Output is correct
18 Correct 55 ms 47188 KB Output is correct
19 Correct 55 ms 47296 KB Output is correct
20 Correct 55 ms 47284 KB Output is correct
21 Correct 54 ms 47284 KB Output is correct
22 Correct 56 ms 47296 KB Output is correct
23 Correct 29 ms 47188 KB Output is correct
24 Correct 27 ms 47252 KB Output is correct
25 Correct 30 ms 47188 KB Output is correct
26 Correct 58 ms 47240 KB Output is correct
27 Correct 28 ms 47188 KB Output is correct
28 Correct 29 ms 47188 KB Output is correct
29 Correct 54 ms 47200 KB Output is correct
30 Correct 28 ms 47188 KB Output is correct
31 Correct 33 ms 47296 KB Output is correct
32 Correct 60 ms 47284 KB Output is correct
33 Correct 29 ms 47180 KB Output is correct
34 Correct 31 ms 47248 KB Output is correct
35 Correct 55 ms 47224 KB Output is correct
36 Correct 27 ms 48304 KB Output is correct
37 Correct 27 ms 48212 KB Output is correct
38 Incorrect 26 ms 48232 KB Output isn't correct
39 Halted 0 ms 0 KB -