oj.uz

Submission #320206

# Submission time Handle Problem Language Result Execution time Memory
320206 2020-11-07T23:34:36 Z Blagojce Duathlon (APIO18_duathlon) C++11
31 / 100
 150 ms 24164 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];

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]++;
	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 rem = locn-sub[u];
	s += rem*rem;
	
	ll all = locn-sz[u];
	
	ll temp = sz[u] * (all*all-s);
	ans += temp;
	ll temp2 = all*(sz[u]-1)*(sz[u]-2)+all*(sz[u]-1);
	ans += 2*temp2;
	
	
	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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9964 KB Output is correct
2 Correct 7 ms 9984 KB Output is correct
3 Correct 7 ms 10092 KB Output is correct
4 Correct 7 ms 9964 KB Output is correct
5 Correct 7 ms 9964 KB Output is correct
6 Correct 7 ms 9964 KB Output is correct
7 Incorrect 7 ms 10092 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9964 KB Output is correct
2 Correct 7 ms 9984 KB Output is correct
3 Correct 7 ms 10092 KB Output is correct
4 Correct 7 ms 9964 KB Output is correct
5 Correct 7 ms 9964 KB Output is correct
6 Correct 7 ms 9964 KB Output is correct
7 Incorrect 7 ms 10092 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 101 ms 22884 KB Output is correct
2 Correct 99 ms 22884 KB Output is correct
3 Correct 110 ms 21476 KB Output is correct
4 Correct 100 ms 23520 KB Output is correct
5 Correct 100 ms 20580 KB Output is correct
6 Correct 113 ms 21700 KB Output is correct
7 Correct 110 ms 20840 KB Output is correct
8 Correct 114 ms 21476 KB Output is correct
9 Correct 103 ms 20104 KB Output is correct
10 Correct 109 ms 20196 KB Output is correct
11 Correct 88 ms 18660 KB Output is correct
12 Correct 84 ms 18532 KB Output is correct
13 Correct 78 ms 18660 KB Output is correct
14 Correct 77 ms 18404 KB Output is correct
15 Correct 67 ms 18168 KB Output is correct
16 Correct 60 ms 17764 KB Output is correct
17 Correct 11 ms 12652 KB Output is correct
18 Correct 11 ms 12652 KB Output is correct
19 Correct 11 ms 12652 KB Output is correct
20 Correct 11 ms 12780 KB Output is correct
21 Correct 11 ms 12524 KB Output is correct
22 Correct 11 ms 12672 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10240 KB Output is correct
2 Correct 8 ms 10092 KB Output is correct
3 Correct 8 ms 10220 KB Output is correct
4 Correct 8 ms 10220 KB Output is correct
5 Correct 7 ms 10092 KB Output is correct
6 Correct 8 ms 10092 KB Output is correct
7 Correct 8 ms 10092 KB Output is correct
8 Correct 8 ms 10092 KB Output is correct
9 Correct 8 ms 10092 KB Output is correct
10 Correct 8 ms 10092 KB Output is correct
11 Correct 9 ms 10092 KB Output is correct
12 Correct 8 ms 10092 KB Output is correct
13 Correct 8 ms 10092 KB Output is correct
14 Correct 8 ms 10092 KB Output is correct
15 Correct 9 ms 10092 KB Output is correct
16 Correct 8 ms 10092 KB Output is correct
17 Correct 8 ms 10092 KB Output is correct
18 Correct 8 ms 10092 KB Output is correct
19 Correct 8 ms 10092 KB Output is correct
20 Correct 8 ms 10124 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 20580 KB Output is correct
2 Correct 114 ms 20580 KB Output is correct
3 Correct 113 ms 20580 KB Output is correct
4 Correct 126 ms 20712 KB Output is correct
5 Correct 119 ms 20580 KB Output is correct
6 Correct 150 ms 24164 KB Output is correct
7 Correct 140 ms 23140 KB Output is correct
8 Correct 142 ms 22376 KB Output is correct
9 Correct 144 ms 21860 KB Output is correct
10 Correct 124 ms 20580 KB Output is correct
11 Correct 120 ms 21860 KB Output is correct
12 Correct 114 ms 21988 KB Output is correct
13 Correct 116 ms 21860 KB Output is correct
14 Correct 107 ms 21348 KB Output is correct
15 Correct 94 ms 20708 KB Output is correct
16 Correct 63 ms 18532 KB Output is correct
17 Correct 69 ms 22356 KB Output is correct
18 Correct 75 ms 22352 KB Output is correct
19 Correct 74 ms 22604 KB Output is correct
20 Correct 80 ms 22356 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10092 KB Output is correct
2 Correct 8 ms 10092 KB Output is correct
3 Incorrect 7 ms 10092 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 20576 KB Output is correct
2 Correct 123 ms 20452 KB Output is correct
3 Incorrect 117 ms 19228 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9964 KB Output is correct
2 Correct 7 ms 9984 KB Output is correct
3 Correct 7 ms 10092 KB Output is correct
4 Correct 7 ms 9964 KB Output is correct
5 Correct 7 ms 9964 KB Output is correct
6 Correct 7 ms 9964 KB Output is correct
7 Incorrect 7 ms 10092 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9964 KB Output is correct
2 Correct 7 ms 9984 KB Output is correct
3 Correct 7 ms 10092 KB Output is correct
4 Correct 7 ms 9964 KB Output is correct
5 Correct 7 ms 9964 KB Output is correct
6 Correct 7 ms 9964 KB Output is correct
7 Incorrect 7 ms 10092 KB Output isn't correct
8 Halted 0 ms 0 KB -