oj.uz

답안 #1021732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1021732 2024-07-13T03:59:20 Z ByeWorld 철인 이종 경기 (APIO18_duathlon) C++14
31 / 100
 109 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;
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 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 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 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 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

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 21344 KB Output is correct
2 Correct 69 ms 22644 KB Output is correct
3 Correct 68 ms 22360 KB Output is correct
4 Correct 65 ms 22568 KB Output is correct
5 Correct 70 ms 20052 KB Output is correct
6 Correct 74 ms 22916 KB Output is correct
7 Correct 69 ms 19796 KB Output is correct
8 Correct 72 ms 21420 KB Output is correct
9 Correct 67 ms 19028 KB Output is correct
10 Correct 66 ms 19280 KB Output is correct
11 Correct 60 ms 18000 KB Output is correct
12 Correct 57 ms 17748 KB Output is correct
13 Correct 53 ms 17976 KB Output is correct
14 Correct 53 ms 17620 KB Output is correct
15 Correct 47 ms 16940 KB Output is correct
16 Correct 43 ms 16464 KB Output is correct
17 Correct 6 ms 10556 KB Output is correct
18 Correct 6 ms 10508 KB Output is correct
19 Correct 6 ms 10588 KB Output is correct
20 Correct 6 ms 10480 KB Output is correct
21 Correct 6 ms 10588 KB Output is correct
22 Correct 6 ms 10588 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5212 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 3 ms 5140 KB Output is correct
4 Correct 3 ms 5208 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 3 ms 5208 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 4 ms 5208 KB Output is correct
13 Correct 3 ms 5208 KB Output is correct
14 Correct 3 ms 5212 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 3 ms 5260 KB Output is correct
17 Correct 2 ms 5212 KB Output is correct
18 Correct 2 ms 5332 KB Output is correct
19 Correct 3 ms 5212 KB Output is correct
20 Correct 2 ms 5212 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 19496 KB Output is correct
2 Correct 72 ms 19416 KB Output is correct
3 Correct 71 ms 19540 KB Output is correct
4 Correct 70 ms 19536 KB Output is correct
5 Correct 77 ms 19524 KB Output is correct
6 Correct 77 ms 27732 KB Output is correct
7 Correct 75 ms 22608 KB Output is correct
8 Correct 109 ms 21844 KB Output is correct
9 Correct 83 ms 20992 KB Output is correct
10 Correct 77 ms 19624 KB Output is correct
11 Correct 70 ms 19544 KB Output is correct
12 Correct 74 ms 19536 KB Output is correct
13 Correct 69 ms 19532 KB Output is correct
14 Correct 68 ms 19280 KB Output is correct
15 Correct 57 ms 18260 KB Output is correct
16 Correct 38 ms 16144 KB Output is correct
17 Correct 54 ms 19908 KB Output is correct
18 Correct 57 ms 19776 KB Output is correct
19 Correct 53 ms 20668 KB Output is correct
20 Correct 60 ms 20096 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 2 ms 5212 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

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 19524 KB Output is correct
2 Correct 73 ms 19264 KB Output is correct
3 Incorrect 62 ms 16208 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 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 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4956 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 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 -