oj.uz

답안 #320690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
320690 2020-11-09T14:11:24 Z Blagojce 철인 이종 경기 (APIO18_duathlon) C++11
66 / 100
 219 ms 34168 KB 
#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define rfr(i, n, m) for(int i = (n); i >= (m); i --)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
#include <deque>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9+1;
const ll inf = 2e18;
const ll mod = 998244353;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
const int mxn = 2e5+5;
mt19937 _rand(time(NULL));

int n, m;

vector<pii> g[mxn];
int l[mxn], r[mxn];
int d[mxn];
bool vis[mxn];
int mind[mxn];
bool bridge[mxn];

vector<int> S[mxn];



void dfs(int u, int p){
	vis[u] = true;
	for(auto e : g[u]){
		if(vis[e.st]){
			if(e.st != p) mind[u] = min(mind[u], d[e.st]);
			continue;
		}
		d[e.st] = d[u]+1;
		mind[e.st] = d[e.st];
		dfs(e.st, u);
		mind[u] = min(mind[u], mind[e.st]);
		if(mind[e.st] > d[u]){
			bridge[e.nd] = true;
		}
	}
}
ll sz[mxn];
int link[mxn];
ll gr;
void dfs2(int u){
	sz[gr]++;
	S[gr].pb(u);
	vis[u] = true;
	link[u] = gr;
	for(auto e : g[u]){
		if(vis[e.st] || bridge[e.nd]) continue;
		dfs2(e.st);
	}
}

vector<int> v[mxn];
ll sub[mxn];
ll ans = 0;
ll locn;
void dfs30(int u){
	locn += sz[u];
	vis[u] = true;
	for(auto e : v[u]){
		if(vis[e]) continue;
		dfs30(e);
	}
}

void dfs3(int u, int p){
	sub[u] = sz[u];
	ll s = 0; 
	
	for(auto e : v[u]){
		if(e == p) continue;
		dfs3(e, u);
		sub[u] += sub[e];
		s += sub[e]*sub[e];
	}
	ll Cnt1 = 0;
	ll Cnt2 = 0;
	for(auto c : S[u]){
		ll cnt1 = 0;
		ll cnt2 = 0;
		
		for(auto e : g[c]){
			if(!bridge[e.nd]) continue;
			if(link[e.st] == p){
				ll csub = locn-sub[u];
				cnt1 += csub;
				cnt2 += csub*csub;
			}
			else{
				ll csub = sub[link[e.st]];
				cnt1 += csub;
				cnt2 += csub*csub;
			}
		}
		ans += cnt1*cnt1-cnt2;
		Cnt1 += cnt1;
		Cnt2 += cnt1*cnt1;
	}

	
	ans += sz[u]*(Cnt1*Cnt1-Cnt2);
	ans += 2 * (Cnt1*(sz[u]-1)*(sz[u]-2) + Cnt1*(sz[u]-1));
	ans += sz[u]*(sz[u]-1)*(sz[u]-2);

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	fr(i, 0, m){
		cin >> l[i] >> r[i];
		--l[i], --r[i];
		g[l[i]].pb({r[i], i});
		g[r[i]].pb({l[i], i});
	}
	fr(i, 0, n) mind[i] = n;
	fr(i, 0, n){
		if(vis[i]) continue;
		dfs(i, i);
	}	
	memset(vis, false, sizeof(vis));
	fr(i, 0, n){
		if(vis[i]) continue;
		dfs2(i);
		++gr;
	}
	
	fr(i, 0, m){
		if(!bridge[i]) continue;
		int a = link[l[i]];
		int b = link[r[i]];
		v[a].pb(b);
		v[b].pb(a);
	}
	memset(vis, false, sizeof(vis));
	
	fr(i, 0, gr){
		if(vis[i]) continue;
		locn = 0;
		dfs30(i);
		dfs3(i, 0);
	
	}
	
	cout<<ans<<endl;
	
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14700 KB Output is correct
2 Correct 10 ms 14700 KB Output is correct
3 Correct 10 ms 14700 KB Output is correct
4 Correct 11 ms 14700 KB Output is correct
5 Correct 10 ms 14700 KB Output is correct
6 Correct 12 ms 14696 KB Output is correct
7 Correct 11 ms 14700 KB Output is correct
8 Incorrect 10 ms 14700 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14700 KB Output is correct
2 Correct 10 ms 14700 KB Output is correct
3 Correct 10 ms 14700 KB Output is correct
4 Correct 11 ms 14700 KB Output is correct
5 Correct 10 ms 14700 KB Output is correct
6 Correct 12 ms 14696 KB Output is correct
7 Correct 11 ms 14700 KB Output is correct
8 Incorrect 10 ms 14700 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 29576 KB Output is correct
2 Correct 124 ms 29520 KB Output is correct
3 Correct 169 ms 29212 KB Output is correct
4 Correct 122 ms 29404 KB Output is correct
5 Correct 135 ms 26708 KB Output is correct
6 Correct 155 ms 28896 KB Output is correct
7 Correct 151 ms 27748 KB Output is correct
8 Correct 179 ms 28132 KB Output is correct
9 Correct 150 ms 26980 KB Output is correct
10 Correct 148 ms 26724 KB Output is correct
11 Correct 133 ms 25444 KB Output is correct
12 Correct 112 ms 25444 KB Output is correct
13 Correct 127 ms 25572 KB Output is correct
14 Correct 120 ms 25316 KB Output is correct
15 Correct 95 ms 25396 KB Output is correct
16 Correct 86 ms 25060 KB Output is correct
17 Correct 21 ms 20460 KB Output is correct
18 Correct 21 ms 20460 KB Output is correct
19 Correct 20 ms 20460 KB Output is correct
20 Correct 20 ms 20460 KB Output is correct
21 Correct 20 ms 20460 KB Output is correct
22 Correct 27 ms 20324 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14828 KB Output is correct
2 Correct 10 ms 14828 KB Output is correct
3 Correct 10 ms 14828 KB Output is correct
4 Correct 11 ms 14828 KB Output is correct
5 Correct 11 ms 14828 KB Output is correct
6 Correct 12 ms 14828 KB Output is correct
7 Correct 13 ms 14828 KB Output is correct
8 Correct 11 ms 14828 KB Output is correct
9 Correct 10 ms 14828 KB Output is correct
10 Correct 11 ms 14828 KB Output is correct
11 Correct 11 ms 14828 KB Output is correct
12 Correct 10 ms 14828 KB Output is correct
13 Correct 11 ms 14828 KB Output is correct
14 Correct 10 ms 14828 KB Output is correct
15 Correct 11 ms 14828 KB Output is correct
16 Correct 11 ms 14824 KB Output is correct
17 Correct 14 ms 14828 KB Output is correct
18 Correct 10 ms 14828 KB Output is correct
19 Correct 10 ms 14828 KB Output is correct
20 Correct 10 ms 14828 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 29688 KB Output is correct
2 Correct 176 ms 29668 KB Output is correct
3 Correct 178 ms 29668 KB Output is correct
4 Correct 171 ms 29796 KB Output is correct
5 Correct 184 ms 29668 KB Output is correct
6 Correct 211 ms 34168 KB Output is correct
7 Correct 204 ms 32864 KB Output is correct
8 Correct 185 ms 31844 KB Output is correct
9 Correct 219 ms 31076 KB Output is correct
10 Correct 164 ms 29668 KB Output is correct
11 Correct 160 ms 29668 KB Output is correct
12 Correct 193 ms 29796 KB Output is correct
13 Correct 185 ms 29668 KB Output is correct
14 Correct 146 ms 29156 KB Output is correct
15 Correct 139 ms 28644 KB Output is correct
16 Correct 121 ms 26340 KB Output is correct
17 Correct 122 ms 30292 KB Output is correct
18 Correct 112 ms 30164 KB Output is correct
19 Correct 116 ms 30412 KB Output is correct
20 Correct 124 ms 30304 KB Output is correct

Subtask #6
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14828 KB Output is correct
2 Correct 10 ms 14828 KB Output is correct
3 Correct 10 ms 14828 KB Output is correct
4 Correct 10 ms 14828 KB Output is correct
5 Correct 11 ms 14828 KB Output is correct
6 Correct 10 ms 14700 KB Output is correct
7 Correct 10 ms 14700 KB Output is correct
8 Correct 10 ms 14700 KB Output is correct
9 Correct 10 ms 14700 KB Output is correct
10 Correct 11 ms 14700 KB Output is correct
11 Correct 10 ms 14700 KB Output is correct
12 Correct 10 ms 14828 KB Output is correct
13 Correct 10 ms 14828 KB Output is correct
14 Correct 10 ms 14828 KB Output is correct
15 Correct 10 ms 14828 KB Output is correct
16 Correct 11 ms 14848 KB Output is correct
17 Correct 10 ms 14828 KB Output is correct
18 Correct 10 ms 14828 KB Output is correct
19 Correct 10 ms 14828 KB Output is correct
20 Correct 11 ms 14828 KB Output is correct
21 Correct 11 ms 14828 KB Output is correct
22 Correct 10 ms 14828 KB Output is correct
23 Correct 12 ms 14828 KB Output is correct
24 Correct 11 ms 14828 KB Output is correct
25 Correct 12 ms 14700 KB Output is correct
26 Correct 12 ms 14700 KB Output is correct
27 Correct 10 ms 14700 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 29620 KB Output is correct
2 Correct 184 ms 29540 KB Output is correct
3 Correct 159 ms 27396 KB Output is correct
4 Correct 140 ms 25444 KB Output is correct
5 Correct 117 ms 23780 KB Output is correct
6 Correct 110 ms 23140 KB Output is correct
7 Correct 109 ms 22756 KB Output is correct
8 Correct 109 ms 22368 KB Output is correct
9 Correct 115 ms 22392 KB Output is correct
10 Correct 96 ms 22116 KB Output is correct
11 Correct 106 ms 21988 KB Output is correct
12 Correct 106 ms 21988 KB Output is correct
13 Correct 94 ms 21988 KB Output is correct
14 Correct 97 ms 23800 KB Output is correct
15 Correct 173 ms 30564 KB Output is correct
16 Correct 161 ms 29416 KB Output is correct
17 Correct 158 ms 29156 KB Output is correct
18 Correct 180 ms 28132 KB Output is correct
19 Correct 146 ms 25572 KB Output is correct
20 Correct 140 ms 25444 KB Output is correct
21 Correct 135 ms 25548 KB Output is correct
22 Correct 130 ms 25060 KB Output is correct
23 Correct 115 ms 24296 KB Output is correct
24 Correct 149 ms 27612 KB Output is correct
25 Correct 141 ms 27744 KB Output is correct
26 Correct 123 ms 26332 KB Output is correct
27 Correct 136 ms 26340 KB Output is correct

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14700 KB Output is correct
2 Correct 10 ms 14700 KB Output is correct
3 Correct 10 ms 14700 KB Output is correct
4 Correct 11 ms 14700 KB Output is correct
5 Correct 10 ms 14700 KB Output is correct
6 Correct 12 ms 14696 KB Output is correct
7 Correct 11 ms 14700 KB Output is correct
8 Incorrect 10 ms 14700 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14700 KB Output is correct
2 Correct 10 ms 14700 KB Output is correct
3 Correct 10 ms 14700 KB Output is correct
4 Correct 11 ms 14700 KB Output is correct
5 Correct 10 ms 14700 KB Output is correct
6 Correct 12 ms 14696 KB Output is correct
7 Correct 11 ms 14700 KB Output is correct
8 Incorrect 10 ms 14700 KB Output isn't correct
9 Halted 0 ms 0 KB -