oj.uz

Submission #1021759

# Submission time Handle Problem Language Result Execution time Memory
1021759 2024-07-13T04:49:58 Z ByeWorld Duathlon (APIO18_duathlon) C++14
31 / 100
 628 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;
const vector<int> NOL = {};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};
const int MOD = 1e9+7;
void chmx(int &a, int b){ a = max(a, b); }
int sum(int a, int b){ return (a+b)%MOD; }
int mul(int a, int b){ return (a*b)%MOD; }
void chsum(int &a, int b){ a = sum(a,b); }

int n, m;
int u[MAXN], v[MAXN];
vector <int> adj[MAXN];
int disc[MAXN], low[MAXN], tim;
int ap[MAXN], color, col[MAXN];
vector <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];
}
int tot = 0;
void cnt(int nw, int par){
	if(par!=0) tot += val[nw];
	if(val[nw]==1) return;
	for(auto nx : edge[nw]){
		if(nx==par) continue;
		cnt(nx, 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].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(auto in : edge[i]) cout << in << ' ';
		// 	cout << i << "i\n";
	}
	// 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<=n; i++)
		if(!sub[i]){ 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;
		}
	}
	// cout << ANS << " ans3\n";
	for(int i=1; i<=color; i++){
		if(val[i]>=2){
			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 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5196 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Runtime error 628 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 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5196 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Runtime error 628 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 68 ms 21840 KB Output is correct
2 Correct 71 ms 21840 KB Output is correct
3 Correct 71 ms 23124 KB Output is correct
4 Correct 75 ms 21976 KB Output is correct
5 Correct 70 ms 20792 KB Output is correct
6 Correct 76 ms 23716 KB Output is correct
7 Correct 79 ms 20720 KB Output is correct
8 Correct 72 ms 22100 KB Output is correct
9 Correct 69 ms 19684 KB Output is correct
10 Correct 68 ms 20052 KB Output is correct
11 Correct 63 ms 18736 KB Output is correct
12 Correct 58 ms 18548 KB Output is correct
13 Correct 56 ms 18772 KB Output is correct
14 Correct 65 ms 18304 KB Output is correct
15 Correct 45 ms 17720 KB Output is correct
16 Correct 57 ms 17232 KB Output is correct
17 Correct 6 ms 10712 KB Output is correct
18 Correct 6 ms 10844 KB Output is correct
19 Correct 6 ms 10584 KB Output is correct
20 Correct 8 ms 10844 KB Output is correct
21 Correct 6 ms 10332 KB Output is correct
22 Correct 6 ms 10332 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 21536 KB Output is correct
2 Correct 72 ms 21540 KB Output is correct
3 Correct 75 ms 21588 KB Output is correct
4 Correct 81 ms 21584 KB Output is correct
5 Correct 72 ms 21660 KB Output is correct
6 Correct 83 ms 29720 KB Output is correct
7 Correct 82 ms 24656 KB Output is correct
8 Correct 81 ms 23896 KB Output is correct
9 Correct 86 ms 23068 KB Output is correct
10 Correct 91 ms 21584 KB Output is correct
11 Correct 72 ms 21612 KB Output is correct
12 Correct 79 ms 21600 KB Output is correct
13 Correct 73 ms 21588 KB Output is correct
14 Correct 67 ms 20724 KB Output is correct
15 Correct 60 ms 20192 KB Output is correct
16 Correct 52 ms 17488 KB Output is correct
17 Correct 82 ms 20480 KB Output is correct
18 Correct 68 ms 20420 KB Output is correct
19 Correct 70 ms 21184 KB Output is correct
20 Correct 63 ms 20544 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Runtime error 615 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 80 ms 21584 KB Output is correct
2 Correct 80 ms 21332 KB Output is correct
3 Runtime error 573 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 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5196 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Runtime error 628 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 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 5196 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Runtime error 628 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -