oj.uz

Submission #1021816

# Submission time Handle Problem Language Result Execution time Memory
1021816 2024-07-13T05:38:54 Z ByeWorld Duathlon (APIO18_duathlon) C++14
31 / 100
 85 ms 34656 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 done[MAXN], DONE;
int n, m;
int u[MAXN], v[MAXN];
vector <int> adj[MAXN];
int disc[MAXN], low[MAXN], tim, chi[MAXN];
int ap[MAXN], color, col[MAXN];
int sub[MAXN], val[MAXN];

int cnt[MAXN];
void dfs(int nw, int par){
	done[nw] = DONE;
	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){
	done[nw] = DONE;
	col[nw] = ty; val[ty]++;
	for(auto nx : adj[nw]){
		if(ap[nx]==1 || col[nx]!=0) continue;
		COL(nx, ty);
	}
}

vector <int> edge[MAXN];
int ANS, root[MAXN];
void trav(int nw, int par, int roo){
	cnt[nw]++;
	if(cnt[nw]>1) assert(false);
	//S - C - F
	done[nw] = DONE;
	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]);
	}
	DONE++;
	for(int i=1; i<=n; i++){
		if(done[i]!=DONE) dfs(i, 0);
	}
	DONE++;
	for(int i=1; i<=n; i++){
		if(col[i]==0) 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].pb(y); edge[y].pb(x);
	}
	for(int i=1; i<=color; i++){
		sort(edge[i].begin(), edge[i].end());
		edge[i].resize(unique(edge[i].begin(), edge[i].end())-edge[i].begin());
	}
	// 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";
	// }
	DONE++;
	for(int i=1; i<=color; i++){
		if(done[i]!=DONE){ trav(i, -1, i); bd(i, -1); }
	}
	// 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 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Runtime error 6 ms 13660 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Runtime error 6 ms 13660 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 19792 KB Output is correct
2 Correct 64 ms 19800 KB Output is correct
3 Correct 71 ms 22352 KB Output is correct
4 Correct 64 ms 20544 KB Output is correct
5 Correct 66 ms 19540 KB Output is correct
6 Correct 68 ms 23068 KB Output is correct
7 Correct 67 ms 19936 KB Output is correct
8 Correct 70 ms 21588 KB Output is correct
9 Correct 74 ms 19024 KB Output is correct
10 Correct 68 ms 19172 KB Output is correct
11 Correct 60 ms 18796 KB Output is correct
12 Correct 58 ms 18516 KB Output is correct
13 Correct 57 ms 19028 KB Output is correct
14 Correct 57 ms 18512 KB Output is correct
15 Correct 53 ms 18300 KB Output is correct
16 Correct 43 ms 18256 KB Output is correct
17 Correct 6 ms 12892 KB Output is correct
18 Correct 8 ms 13148 KB Output is correct
19 Correct 7 ms 12888 KB Output is correct
20 Correct 6 ms 12120 KB Output is correct
21 Correct 6 ms 12636 KB Output is correct
22 Correct 6 ms 12636 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7004 KB Output is correct
2 Correct 3 ms 7004 KB Output is correct
3 Correct 2 ms 6888 KB Output is correct
4 Correct 3 ms 6232 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 3 ms 6236 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 2 ms 6852 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7000 KB Output is correct
13 Correct 3 ms 7008 KB Output is correct
14 Correct 3 ms 7004 KB Output is correct
15 Correct 2 ms 7004 KB Output is correct
16 Correct 2 ms 7004 KB Output is correct
17 Correct 2 ms 7004 KB Output is correct
18 Correct 3 ms 6232 KB Output is correct
19 Correct 3 ms 7256 KB Output is correct
20 Correct 2 ms 6236 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 21820 KB Output is correct
2 Correct 74 ms 21796 KB Output is correct
3 Correct 84 ms 21784 KB Output is correct
4 Correct 73 ms 21844 KB Output is correct
5 Correct 77 ms 21844 KB Output is correct
6 Correct 83 ms 30036 KB Output is correct
7 Correct 79 ms 24908 KB Output is correct
8 Correct 85 ms 24132 KB Output is correct
9 Correct 81 ms 23220 KB Output is correct
10 Correct 73 ms 21844 KB Output is correct
11 Correct 77 ms 21840 KB Output is correct
12 Correct 77 ms 21752 KB Output is correct
13 Correct 81 ms 21840 KB Output is correct
14 Correct 70 ms 21332 KB Output is correct
15 Correct 62 ms 20564 KB Output is correct
16 Correct 40 ms 18780 KB Output is correct
17 Correct 64 ms 20672 KB Output is correct
18 Correct 61 ms 20800 KB Output is correct
19 Correct 64 ms 21432 KB Output is correct
20 Correct 62 ms 20888 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Runtime error 7 ms 13960 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 21928 KB Output is correct
2 Correct 75 ms 21592 KB Output is correct
3 Runtime error 69 ms 34656 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Runtime error 6 ms 13660 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Runtime error 6 ms 13660 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -