oj.uz

Submission #1021741

# Submission time Handle Problem Language Result Execution time Memory
1021741 2024-07-13T04:11:29 Z ByeWorld Duathlon (APIO18_duathlon) C++14
31 / 100
 96 ms 29068 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];

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 {
			dfs(nx, nw);
			low[nw] = min(low[nw], low[nx]);
		}
	}
	if(disc[nw]==low[nw] || (adj[nw].size()>=2 && nw==1)){
		ap[nw] = 1; 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<=n; i++)
		if(!sub[i]){ trav(i, 0, i); bd(i, 0); }
	// SCF
	for(int i=1; i<=color; i++){
		if(val[i]>=3) ANS += val[i]*(val[i]-1)*(val[i]-2);
	}
	// 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;

			tot = 0;
			cnt(i, 0);
			ANS += val[i]*(val[i]-1)*tot;
		}
	}
	// for(int i=1; i<=color; i++){
	// 	cout << i << ' ' << val[i] << " val\n";
	// }

	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 3 ms 5212 KB Output is correct
3 Correct 2 ms 5160 KB Output is correct
4 Correct 2 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 Incorrect 2 ms 4956 KB Output isn't correct
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 3 ms 5212 KB Output is correct
3 Correct 2 ms 5160 KB Output is correct
4 Correct 2 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 Incorrect 2 ms 4956 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 22612 KB Output is correct
2 Correct 63 ms 22612 KB Output is correct
3 Correct 67 ms 22352 KB Output is correct
4 Correct 65 ms 22352 KB Output is correct
5 Correct 72 ms 20052 KB Output is correct
6 Correct 70 ms 22968 KB Output is correct
7 Correct 72 ms 19792 KB Output is correct
8 Correct 69 ms 21344 KB Output is correct
9 Correct 74 ms 18988 KB Output is correct
10 Correct 68 ms 19280 KB Output is correct
11 Correct 58 ms 18008 KB Output is correct
12 Correct 58 ms 17792 KB Output is correct
13 Correct 58 ms 17748 KB Output is correct
14 Correct 56 ms 17488 KB Output is correct
15 Correct 45 ms 16824 KB Output is correct
16 Correct 42 ms 16672 KB Output is correct
17 Correct 6 ms 10588 KB Output is correct
18 Correct 9 ms 10584 KB Output is correct
19 Correct 6 ms 10584 KB Output is correct
20 Correct 6 ms 10588 KB Output is correct
21 Correct 6 ms 10532 KB Output is correct
22 Correct 5 ms 10504 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 5176 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 3 ms 5212 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5208 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 5 ms 5296 KB Output is correct
11 Correct 3 ms 5208 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 2 ms 5212 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 3 ms 5212 KB Output is correct
17 Correct 3 ms 5160 KB Output is correct
18 Correct 2 ms 5212 KB Output is correct
19 Correct 2 ms 5168 KB Output is correct
20 Correct 2 ms 5212 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 20756 KB Output is correct
2 Correct 72 ms 20816 KB Output is correct
3 Correct 91 ms 20816 KB Output is correct
4 Correct 70 ms 20820 KB Output is correct
5 Correct 70 ms 20816 KB Output is correct
6 Correct 85 ms 29068 KB Output is correct
7 Correct 77 ms 23880 KB Output is correct
8 Correct 76 ms 23128 KB Output is correct
9 Correct 96 ms 22100 KB Output is correct
10 Correct 74 ms 20860 KB Output is correct
11 Correct 75 ms 20820 KB Output is correct
12 Correct 83 ms 20664 KB Output is correct
13 Correct 73 ms 20816 KB Output is correct
14 Correct 66 ms 19984 KB Output is correct
15 Correct 57 ms 19288 KB Output is correct
16 Correct 40 ms 16724 KB Output is correct
17 Correct 53 ms 21104 KB Output is correct
18 Correct 53 ms 21236 KB Output is correct
19 Correct 54 ms 21944 KB Output is correct
20 Correct 53 ms 21312 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 2 ms 5216 KB Output is correct
3 Incorrect 3 ms 5212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 20816 KB Output is correct
2 Correct 71 ms 20564 KB Output is correct
3 Incorrect 57 ms 17488 KB Output isn't correct
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 3 ms 5212 KB Output is correct
3 Correct 2 ms 5160 KB Output is correct
4 Correct 2 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 Incorrect 2 ms 4956 KB Output isn't correct
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 3 ms 5212 KB Output is correct
3 Correct 2 ms 5160 KB Output is correct
4 Correct 2 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 Incorrect 2 ms 4956 KB Output isn't correct
8 Halted 0 ms 0 KB -