oj.uz

Submission #1021737

# Submission time Handle Problem Language Result Execution time Memory
1021737 2024-07-13T04:05:13 Z ByeWorld Duathlon (APIO18_duathlon) C++14
31 / 100
 123 ms 27732 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];
}
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;

			int oth = 0; // C - SF
			for(auto nx : edge[i]){
				oth += val[nx];
			}
			ANS += val[i]*(val[i]-1)*oth;
		}
	}
	// 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 3 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 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 4952 KB Output is correct
7 Incorrect 2 ms 4952 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 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 4952 KB Output is correct
7 Incorrect 2 ms 4952 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 72 ms 21332 KB Output is correct
2 Correct 62 ms 21548 KB Output is correct
3 Correct 102 ms 21076 KB Output is correct
4 Correct 70 ms 21148 KB Output is correct
5 Correct 80 ms 18824 KB Output is correct
6 Correct 73 ms 21860 KB Output is correct
7 Correct 72 ms 18512 KB Output is correct
8 Correct 75 ms 20152 KB Output is correct
9 Correct 68 ms 17744 KB Output is correct
10 Correct 97 ms 18000 KB Output is correct
11 Correct 63 ms 17012 KB Output is correct
12 Correct 60 ms 16756 KB Output is correct
13 Correct 61 ms 16980 KB Output is correct
14 Correct 53 ms 16620 KB Output is correct
15 Correct 58 ms 16212 KB Output is correct
16 Correct 43 ms 15972 KB Output is correct
17 Correct 5 ms 10584 KB Output is correct
18 Correct 6 ms 10588 KB Output is correct
19 Correct 6 ms 10528 KB Output is correct
20 Correct 6 ms 10588 KB Output is correct
21 Correct 9 ms 10588 KB Output is correct
22 Correct 5 ms 10584 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 5208 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 5208 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5464 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 3 ms 5212 KB Output is correct
13 Correct 4 ms 5328 KB Output is correct
14 Correct 3 ms 5312 KB Output is correct
15 Correct 3 ms 5224 KB Output is correct
16 Correct 3 ms 5188 KB Output is correct
17 Correct 4 ms 5212 KB Output is correct
18 Correct 3 ms 5212 KB Output is correct
19 Correct 3 ms 5464 KB Output is correct
20 Correct 3 ms 5208 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 19536 KB Output is correct
2 Correct 77 ms 19540 KB Output is correct
3 Correct 86 ms 19540 KB Output is correct
4 Correct 87 ms 19516 KB Output is correct
5 Correct 87 ms 19540 KB Output is correct
6 Correct 83 ms 27732 KB Output is correct
7 Correct 123 ms 22756 KB Output is correct
8 Correct 79 ms 21792 KB Output is correct
9 Correct 79 ms 20864 KB Output is correct
10 Correct 77 ms 19540 KB Output is correct
11 Correct 99 ms 19536 KB Output is correct
12 Correct 75 ms 19420 KB Output is correct
13 Correct 90 ms 19408 KB Output is correct
14 Correct 68 ms 19024 KB Output is correct
15 Correct 85 ms 18256 KB Output is correct
16 Correct 38 ms 16188 KB Output is correct
17 Correct 55 ms 19908 KB Output is correct
18 Correct 63 ms 19780 KB Output is correct
19 Correct 57 ms 20676 KB Output is correct
20 Correct 58 ms 20036 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 5212 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 76 ms 19536 KB Output is correct
2 Correct 90 ms 19276 KB Output is correct
3 Incorrect 64 ms 16032 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 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 4952 KB Output is correct
7 Incorrect 2 ms 4952 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 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 4952 KB Output is correct
7 Incorrect 2 ms 4952 KB Output isn't correct
8 Halted 0 ms 0 KB -