oj.uz

Submission #1021731

# Submission time Handle Problem Language Result Execution time Memory
1021731 2024-07-13T03:58:11 Z ByeWorld Duathlon (APIO18_duathlon) C++14
23 / 100
 98 ms 29008 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)/6;
	}
	// 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;
			for(auto nx : edge[i]){
				if(val[nx]==1) oth++;
			}
			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 Incorrect 2 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 22772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 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 5212 KB Output is correct
5 Correct 2 ms 5176 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 5212 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 3 ms 5212 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 3 ms 5212 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 2 ms 5288 KB Output is correct
17 Correct 4 ms 5212 KB Output is correct
18 Correct 3 ms 5208 KB Output is correct
19 Correct 2 ms 5212 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 71 ms 20864 KB Output is correct
2 Correct 73 ms 20820 KB Output is correct
3 Correct 76 ms 20684 KB Output is correct
4 Correct 79 ms 20860 KB Output is correct
5 Correct 71 ms 20820 KB Output is correct
6 Correct 78 ms 29008 KB Output is correct
7 Correct 88 ms 23988 KB Output is correct
8 Correct 90 ms 23064 KB Output is correct
9 Correct 81 ms 22352 KB Output is correct
10 Correct 71 ms 20820 KB Output is correct
11 Correct 71 ms 20820 KB Output is correct
12 Correct 98 ms 20820 KB Output is correct
13 Correct 71 ms 20720 KB Output is correct
14 Correct 71 ms 20048 KB Output is correct
15 Correct 59 ms 19224 KB Output is correct
16 Correct 40 ms 16772 KB Output is correct
17 Correct 66 ms 21060 KB Output is correct
18 Correct 55 ms 21056 KB Output is correct
19 Correct 55 ms 21808 KB Output is correct
20 Correct 55 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 3 ms 5184 KB Output is correct
3 Incorrect 2 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 71 ms 20872 KB Output is correct
2 Correct 71 ms 20556 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 Incorrect 2 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -