oj.uz

Submission #1021814

# Submission time Handle Problem Language Result Execution time Memory
1021814 2024-07-13T05:38:19 Z ByeWorld Duathlon (APIO18_duathlon) C++14
31 / 100
 672 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 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(done[nx]==DONE) 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 1 ms 8540 KB Output is correct
2 Correct 1 ms 8636 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Runtime error 672 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 1 ms 8540 KB Output is correct
2 Correct 1 ms 8636 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Runtime error 672 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 83 ms 20564 KB Output is correct
2 Correct 79 ms 20564 KB Output is correct
3 Correct 78 ms 22172 KB Output is correct
4 Correct 77 ms 21908 KB Output is correct
5 Correct 72 ms 20320 KB Output is correct
6 Correct 77 ms 22812 KB Output is correct
7 Correct 81 ms 20404 KB Output is correct
8 Correct 76 ms 21660 KB Output is correct
9 Correct 76 ms 19656 KB Output is correct
10 Correct 75 ms 19192 KB Output is correct
11 Correct 74 ms 18772 KB Output is correct
12 Correct 78 ms 18524 KB Output is correct
13 Correct 55 ms 18772 KB Output is correct
14 Correct 61 ms 18708 KB Output is correct
15 Correct 48 ms 18260 KB Output is correct
16 Correct 49 ms 17988 KB Output is correct
17 Correct 6 ms 12900 KB Output is correct
18 Correct 9 ms 13144 KB Output is correct
19 Correct 6 ms 12936 KB Output is correct
20 Correct 6 ms 12892 KB Output is correct
21 Correct 6 ms 12636 KB Output is correct
22 Correct 6 ms 11828 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 4 ms 6488 KB Output is correct
3 Correct 3 ms 6344 KB Output is correct
4 Correct 3 ms 6236 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 3 ms 7004 KB Output is correct
7 Correct 4 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 2 ms 7004 KB Output is correct
10 Correct 3 ms 7004 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7000 KB Output is correct
13 Correct 2 ms 7004 KB Output is correct
14 Correct 2 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 2 ms 6488 KB Output is correct
19 Correct 2 ms 7004 KB Output is correct
20 Correct 2 ms 7004 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 21844 KB Output is correct
2 Correct 71 ms 21964 KB Output is correct
3 Correct 72 ms 21832 KB Output is correct
4 Correct 76 ms 21844 KB Output is correct
5 Correct 83 ms 22096 KB Output is correct
6 Correct 77 ms 28356 KB Output is correct
7 Correct 103 ms 24400 KB Output is correct
8 Correct 80 ms 23632 KB Output is correct
9 Correct 79 ms 23120 KB Output is correct
10 Correct 73 ms 21908 KB Output is correct
11 Correct 75 ms 21840 KB Output is correct
12 Correct 78 ms 21788 KB Output is correct
13 Correct 75 ms 21840 KB Output is correct
14 Correct 69 ms 21404 KB Output is correct
15 Correct 61 ms 20564 KB Output is correct
16 Correct 40 ms 18512 KB Output is correct
17 Correct 66 ms 20672 KB Output is correct
18 Correct 64 ms 20800 KB Output is correct
19 Correct 68 ms 21532 KB Output is correct
20 Correct 66 ms 20800 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 3 ms 7004 KB Output is correct
3 Runtime error 647 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 73 ms 21876 KB Output is correct
2 Correct 78 ms 21652 KB Output is correct
3 Runtime error 638 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 1 ms 8540 KB Output is correct
2 Correct 1 ms 8636 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Runtime error 672 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 1 ms 8540 KB Output is correct
2 Correct 1 ms 8636 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Runtime error 672 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -