oj.uz

Submission #1021812

# Submission time Handle Problem Language Result Execution time Memory
1021812 2024-07-13T05:37:11 Z ByeWorld Duathlon (APIO18_duathlon) C++14
31 / 100
 84 ms 37712 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, 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 2 ms 7516 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 7516 KB Output is correct
7 Runtime error 7 ms 17244 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 7516 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 7516 KB Output is correct
7 Runtime error 7 ms 17244 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 62 ms 21588 KB Output is correct
2 Correct 64 ms 21588 KB Output is correct
3 Correct 68 ms 22608 KB Output is correct
4 Correct 63 ms 22096 KB Output is correct
5 Correct 65 ms 21072 KB Output is correct
6 Correct 68 ms 23444 KB Output is correct
7 Correct 65 ms 20560 KB Output is correct
8 Correct 74 ms 22100 KB Output is correct
9 Correct 64 ms 19792 KB Output is correct
10 Correct 71 ms 20048 KB Output is correct
11 Correct 57 ms 19280 KB Output is correct
12 Correct 59 ms 18776 KB Output is correct
13 Correct 53 ms 19280 KB Output is correct
14 Correct 68 ms 19028 KB Output is correct
15 Correct 40 ms 18516 KB Output is correct
16 Correct 46 ms 18256 KB Output is correct
17 Correct 7 ms 12888 KB Output is correct
18 Correct 5 ms 13148 KB Output is correct
19 Correct 5 ms 12892 KB Output is correct
20 Correct 5 ms 12780 KB Output is correct
21 Correct 5 ms 12552 KB Output is correct
22 Correct 5 ms 12636 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 21952 KB Output is correct
2 Correct 77 ms 21844 KB Output is correct
3 Correct 68 ms 21840 KB Output is correct
4 Correct 67 ms 21840 KB Output is correct
5 Correct 73 ms 21740 KB Output is correct
6 Correct 84 ms 30032 KB Output is correct
7 Correct 76 ms 24916 KB Output is correct
8 Correct 77 ms 24184 KB Output is correct
9 Correct 83 ms 23376 KB Output is correct
10 Correct 75 ms 21960 KB Output is correct
11 Correct 71 ms 21840 KB Output is correct
12 Correct 72 ms 21992 KB Output is correct
13 Correct 76 ms 21840 KB Output is correct
14 Correct 80 ms 21332 KB Output is correct
15 Correct 75 ms 20820 KB Output is correct
16 Correct 37 ms 18772 KB Output is correct
17 Correct 66 ms 20680 KB Output is correct
18 Correct 82 ms 20596 KB Output is correct
19 Correct 60 ms 21436 KB Output is correct
20 Correct 61 ms 20800 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Runtime error 11 ms 17464 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 72 ms 21832 KB Output is correct
2 Correct 81 ms 21516 KB Output is correct
3 Runtime error 71 ms 37712 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 7516 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 7516 KB Output is correct
7 Runtime error 7 ms 17244 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 7516 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 7516 KB Output is correct
7 Runtime error 7 ms 17244 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -