oj.uz

Submission #1021819

# Submission time Handle Problem Language Result Execution time Memory
1021819 2024-07-13T05:41:54 Z ByeWorld Duathlon (APIO18_duathlon) C++14
31 / 100
 89 ms 34704 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){
	cnt[nw]++;
	if(cnt[nw]>2) assert(false);
	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);
	}
	int ED = 0;
	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());
		ED += edge[i].size();
	}
	// cout << ED/2 << "wed\n";
	assert(ED/2<=color-1);
	// 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 7000 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 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6744 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 7000 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 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6744 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 63 ms 19796 KB Output is correct
2 Correct 66 ms 20000 KB Output is correct
3 Correct 72 ms 22352 KB Output is correct
4 Correct 65 ms 20564 KB Output is correct
5 Correct 71 ms 19540 KB Output is correct
6 Correct 70 ms 23108 KB Output is correct
7 Correct 69 ms 20044 KB Output is correct
8 Correct 87 ms 21588 KB Output is correct
9 Correct 89 ms 19028 KB Output is correct
10 Correct 67 ms 19024 KB Output is correct
11 Correct 70 ms 18768 KB Output is correct
12 Correct 61 ms 18512 KB Output is correct
13 Correct 72 ms 18920 KB Output is correct
14 Correct 56 ms 18536 KB Output is correct
15 Correct 44 ms 18516 KB Output is correct
16 Correct 48 ms 18512 KB Output is correct
17 Correct 8 ms 12892 KB Output is correct
18 Correct 6 ms 12936 KB Output is correct
19 Correct 6 ms 12892 KB Output is correct
20 Correct 6 ms 12888 KB Output is correct
21 Correct 6 ms 12636 KB Output is correct
22 Correct 6 ms 11868 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Correct 2 ms 7000 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 2 ms 6232 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 7004 KB Output is correct
11 Correct 3 ms 6232 KB Output is correct
12 Correct 3 ms 6236 KB Output is correct
13 Correct 2 ms 7088 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 3 ms 7004 KB Output is correct
19 Correct 2 ms 7004 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 74 ms 21944 KB Output is correct
2 Correct 78 ms 21876 KB Output is correct
3 Correct 80 ms 21840 KB Output is correct
4 Correct 74 ms 21844 KB Output is correct
5 Correct 72 ms 21840 KB Output is correct
6 Correct 85 ms 30032 KB Output is correct
7 Correct 82 ms 25084 KB Output is correct
8 Correct 81 ms 24132 KB Output is correct
9 Correct 86 ms 23376 KB Output is correct
10 Correct 70 ms 21840 KB Output is correct
11 Correct 71 ms 21840 KB Output is correct
12 Correct 83 ms 21844 KB Output is correct
13 Correct 81 ms 22096 KB Output is correct
14 Correct 72 ms 21332 KB Output is correct
15 Correct 59 ms 20744 KB Output is correct
16 Correct 40 ms 18772 KB Output is correct
17 Correct 77 ms 20656 KB Output is correct
18 Correct 62 ms 20800 KB Output is correct
19 Correct 67 ms 21492 KB Output is correct
20 Correct 61 ms 20892 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 6236 KB Output is correct
3 Runtime error 7 ms 14016 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 21912 KB Output is correct
2 Correct 78 ms 21588 KB Output is correct
3 Runtime error 75 ms 34704 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 7000 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 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6744 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 7000 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 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Runtime error 6 ms 13660 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -