oj.uz

Submission #320198

# Submission time Handle Problem Language Result Execution time Memory
320198 2020-11-07T22:45:34 Z Blagojce Duathlon (APIO18_duathlon) C++11
0 / 100
 128 ms 25316 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;
		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;
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 = n-sub[u];
	s += rem*rem;
	
	ll all = n-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;
	dfs(0, 0);
	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);
	}
	dfs3(0, 0);
	cout<<ans<<endl;
	
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 24052 KB Output is correct
2 Correct 97 ms 24292 KB Output is correct
3 Incorrect 84 ms 20196 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.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 Correct 8 ms 10092 KB Output is correct
4 Correct 8 ms 10220 KB Output is correct
5 Correct 8 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 Incorrect 9 ms 10092 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 21876 KB Output is correct
2 Correct 113 ms 21860 KB Output is correct
3 Correct 119 ms 21992 KB Output is correct
4 Correct 108 ms 21860 KB Output is correct
5 Correct 112 ms 21860 KB Output is correct
6 Correct 128 ms 25316 KB Output is correct
7 Correct 128 ms 24292 KB Output is correct
8 Correct 125 ms 23656 KB Output is correct
9 Correct 126 ms 22880 KB Output is correct
10 Incorrect 95 ms 19684 KB Output isn't correct
11 Halted 0 ms 0 KB -

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 8 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 122 ms 21992 KB Output is correct
2 Correct 113 ms 21604 KB Output is correct
3 Incorrect 114 ms 20580 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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