oj.uz

Submission #1021762

# Submission time Handle Problem Language Result Execution time Memory
1021762 2024-07-13T04:52:28 Z ByeWorld Duathlon (APIO18_duathlon) C++14
31 / 100
 897 ms 1048576 KB 
#include <bits/stdc++.h>
// #pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 1e5+10;
const int MAXA = 9e3+20;
const ll INF = 1e18+10;
const int LOG = 20;
const int SQRT = 450;

int n, m;
int u[MAXN], v[MAXN];
vector <int> adj[MAXN];
int disc[MAXN], low[MAXN], tim;
int ap[MAXN], color, col[MAXN];
set <int> edge[MAXN];
int sub[MAXN], val[MAXN], chi[MAXN];

void dfs(int nw, int par){
	disc[nw] = low[nw] = ++tim;
	for(auto nx : adj[nw]){
		if(nx==par) continue;
		if(disc[nx]!=0) low[nw] = min(low[nw], disc[nx]);
		else {
			chi[nw]++;
			dfs(nx, nw);
			if(nw!=1 && low[nx] >= disc[nw]) ap[nw] = 1; 
			low[nw] = min(low[nw], low[nx]);
		}
	}
	if(chi[nw]>=2 && nw==1) ap[nw] = 1; 
	if(ap[nw]){
		col[nw] = ++color; val[col[nw]] = 1;
	}
}
void COL(int nw, int ty){
	col[nw] = ty; val[ty]++;
	for(auto nx : adj[nw]){
		if(ap[nx]==1 || col[nx]!=0) continue;
		COL(nx, ty);
	}
}

int ANS, root[MAXN];
void trav(int nw, int par, int roo){
	//S - C - F
	int te = 0, bef = 0; root[nw] = roo;
	sub[nw] = val[nw];
	for(auto nx : edge[nw]){
		if(nx==par) continue;
		trav(nx, nw, roo);
		sub[nw] += sub[nx];
		te += bef*sub[nx]*2;
		bef += sub[nx];
	}
	ANS += te*val[nw];
}
void bd(int nw, int par){
	for(auto nx : edge[nw]){
		if(nx==par) continue;
		bd(nx, nw);
	}
	int up = sub[root[nw]]-sub[nw], dw = sub[nw]-val[nw];
	int te = up*dw*2;
	// cout << nw << ' ' << te << " te\n";
	ANS += te*val[nw];
}

signed main(){
	// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i=1; i<=m; i++){
		cin >> u[i] >> v[i];
		adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]);
	}
	for(int i=1; i<=n; i++)
		if(!disc[i]) dfs(i, 0);
	for(int i=1; i<=n; i++){
		if(!col[i]) COL(i, ++color);
	}
	for(int i=1; i<=m; i++){
		int x = col[u[i]], y = col[v[i]];
		if(x==y) continue;
		edge[x].insert(y); edge[y].insert(x);
	}
	// for(int i=1; i<=color; i++){
	// 	cout << i << ' ' << val[i] << " val\n";
	// }
	// for(int i=1; i<=n; i++){
	// 	cout << i << ' ' << disc[i] << ' ' << low[i] << ' ' << chi[i] << ' '<<col[i] << " col\n";
	// }
	for(int i=1; i<=color; i++){
		if(sub[i]==0){ trav(i, 0, i); bd(i, 0); }
	}
	// cout << ANS << " ans1\n";
	// SCF
	for(int i=1; i<=color; i++){
		if(val[i]>=3) ANS += val[i]*(val[i]-1)*(val[i]-2);
	}
	// cout << ANS << " ans2\n";
	// SC-F atau S-CF
	for(int i=1; i<=color; i++){
		if(val[i]>=2){
			int siz = sub[root[i]];
			ANS += val[i]*(val[i]-1)*(siz-val[i])*2;

			int tot = 0;
			for(auto nx : edge[i]) tot += val[nx];
			ANS += val[i]*(val[i]-1)*tot;
		}
	}

	cout << ANS << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 4 ms 7512 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7384 KB Output is correct
7 Runtime error 897 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 4 ms 7512 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7384 KB Output is correct
7 Runtime error 897 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 21552 KB Output is correct
2 Correct 66 ms 21484 KB Output is correct
3 Correct 77 ms 26652 KB Output is correct
4 Correct 65 ms 23636 KB Output is correct
5 Correct 70 ms 22868 KB Output is correct
6 Correct 74 ms 27732 KB Output is correct
7 Correct 73 ms 24916 KB Output is correct
8 Correct 79 ms 26448 KB Output is correct
9 Correct 73 ms 23892 KB Output is correct
10 Correct 75 ms 23324 KB Output is correct
11 Correct 60 ms 22096 KB Output is correct
12 Correct 60 ms 21808 KB Output is correct
13 Correct 56 ms 21840 KB Output is correct
14 Correct 58 ms 21584 KB Output is correct
15 Correct 44 ms 20560 KB Output is correct
16 Correct 49 ms 20308 KB Output is correct
17 Correct 7 ms 12892 KB Output is correct
18 Correct 7 ms 13012 KB Output is correct
19 Correct 6 ms 12888 KB Output is correct
20 Correct 7 ms 12892 KB Output is correct
21 Correct 7 ms 12636 KB Output is correct
22 Correct 7 ms 12632 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 28244 KB Output is correct
2 Correct 101 ms 28240 KB Output is correct
3 Correct 99 ms 28240 KB Output is correct
4 Correct 91 ms 28220 KB Output is correct
5 Correct 90 ms 28396 KB Output is correct
6 Correct 93 ms 37204 KB Output is correct
7 Correct 92 ms 31568 KB Output is correct
8 Correct 94 ms 30820 KB Output is correct
9 Correct 92 ms 29916 KB Output is correct
10 Correct 89 ms 28240 KB Output is correct
11 Correct 110 ms 28312 KB Output is correct
12 Correct 92 ms 28240 KB Output is correct
13 Correct 82 ms 28276 KB Output is correct
14 Correct 79 ms 26960 KB Output is correct
15 Correct 65 ms 25680 KB Output is correct
16 Correct 48 ms 21592 KB Output is correct
17 Correct 91 ms 27064 KB Output is correct
18 Correct 93 ms 26964 KB Output is correct
19 Correct 91 ms 27068 KB Output is correct
20 Correct 98 ms 26944 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 4 ms 7516 KB Output is correct
3 Runtime error 580 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 28356 KB Output is correct
2 Correct 89 ms 28240 KB Output is correct
3 Runtime error 534 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 4 ms 7512 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7384 KB Output is correct
7 Runtime error 897 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 4 ms 7512 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7384 KB Output is correct
7 Runtime error 897 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -