oj.uz

Submission #1021756

# Submission time Handle Problem Language Result Execution time Memory
1021756 2024-07-13T04:43:51 Z ByeWorld Duathlon (APIO18_duathlon) C++14
31 / 100
 691 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] || col[nx]) 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;
			cnt(i, 0);
			ANS += val[i]*(val[i]-1)*tot;
		}
	}

	cout << ANS << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 3 ms 5408 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 5164 KB Output is correct
6 Correct 4 ms 4968 KB Output is correct
7 Runtime error 691 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 3 ms 4952 KB Output is correct
2 Correct 3 ms 5408 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 5164 KB Output is correct
6 Correct 4 ms 4968 KB Output is correct
7 Runtime error 691 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 100 ms 21920 KB Output is correct
2 Correct 71 ms 21844 KB Output is correct
3 Correct 100 ms 22952 KB Output is correct
4 Correct 72 ms 22220 KB Output is correct
5 Correct 106 ms 20856 KB Output is correct
6 Correct 79 ms 23868 KB Output is correct
7 Correct 81 ms 20564 KB Output is correct
8 Correct 82 ms 22092 KB Output is correct
9 Correct 78 ms 19812 KB Output is correct
10 Correct 132 ms 19904 KB Output is correct
11 Correct 71 ms 18716 KB Output is correct
12 Correct 134 ms 18520 KB Output is correct
13 Correct 62 ms 18768 KB Output is correct
14 Correct 73 ms 18252 KB Output is correct
15 Correct 53 ms 17492 KB Output is correct
16 Correct 79 ms 17232 KB Output is correct
17 Correct 7 ms 10588 KB Output is correct
18 Correct 7 ms 10844 KB Output is correct
19 Correct 9 ms 10400 KB Output is correct
20 Correct 6 ms 10588 KB Output is correct
21 Correct 8 ms 10284 KB Output is correct
22 Correct 7 ms 10328 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5212 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 4 ms 5212 KB Output is correct
5 Correct 3 ms 5216 KB Output is correct
6 Correct 4 ms 5176 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5208 KB Output is correct
9 Correct 4 ms 5272 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 3 ms 5208 KB Output is correct
12 Correct 3 ms 5208 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 3 ms 5216 KB Output is correct
15 Correct 4 ms 5212 KB Output is correct
16 Correct 3 ms 5164 KB Output is correct
17 Correct 4 ms 5464 KB Output is correct
18 Correct 3 ms 5212 KB Output is correct
19 Correct 3 ms 5216 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 82 ms 21624 KB Output is correct
2 Correct 87 ms 21588 KB Output is correct
3 Correct 95 ms 21592 KB Output is correct
4 Correct 104 ms 21488 KB Output is correct
5 Correct 81 ms 21584 KB Output is correct
6 Correct 126 ms 29776 KB Output is correct
7 Correct 83 ms 24656 KB Output is correct
8 Correct 139 ms 23712 KB Output is correct
9 Correct 92 ms 22848 KB Output is correct
10 Correct 110 ms 21656 KB Output is correct
11 Correct 84 ms 21584 KB Output is correct
12 Correct 122 ms 21472 KB Output is correct
13 Correct 89 ms 21468 KB Output is correct
14 Correct 98 ms 20816 KB Output is correct
15 Correct 68 ms 20124 KB Output is correct
16 Correct 63 ms 17456 KB Output is correct
17 Correct 76 ms 20452 KB Output is correct
18 Correct 106 ms 20312 KB Output is correct
19 Correct 70 ms 21180 KB Output is correct
20 Correct 111 ms 20552 KB Output is correct

Subtask #6
0 / 15.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 Runtime error 667 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 110 ms 21588 KB Output is correct
2 Correct 137 ms 21332 KB Output is correct
3 Runtime error 575 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 3 ms 4952 KB Output is correct
2 Correct 3 ms 5408 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 5164 KB Output is correct
6 Correct 4 ms 4968 KB Output is correct
7 Runtime error 691 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 3 ms 4952 KB Output is correct
2 Correct 3 ms 5408 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 5164 KB Output is correct
6 Correct 4 ms 4968 KB Output is correct
7 Runtime error 691 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -