oj.uz

Submission #421238

# Submission time Handle Problem Language Result Execution time Memory
421238 2021-06-08T22:36:40 Z Blagojce Duathlon (APIO18_duathlon) C++11
31 / 100
 320 ms 103072 KB 
#include <bits/stdc++.h>
#define fr(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)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
 
mt19937 _rand(time(NULL));
const int mxn = 5e5+5;

int n, m;

vector<pii> g[mxn];

bool vis[mxn];
int low[mxn];
int pre[mxn];

ll artin[mxn];

int pos = 0;

vector<int> art;

stack<int> S;

vector<vector<int> > G;

bool adds[mxn];

void dfs(int u, int p){
	vis[u] = true;
	pre[u] = low[u] = pos ++;
	
	int c = 0;
	for(auto e : g[u]){
		if(e.st == p) continue;
		
		if(!adds[e.nd]){
			adds[e.nd] = true;
			S.push(e.nd);
		}
		if(vis[e.st]){
			low[u] = min(low[u], pre[e.st]);
		}
		else{
			++c;
			dfs(e.st, u);
			low[u] = min(low[u], low[e.st]);
			if(low[e.st] >= pre[u] && p != -1){
				art.pb(u);
			}
			if((low[e.st] >= pre[u] && p != -1) || (p == -1 && c > 1)){
				vector<int> comp;
				while(S.top() != e.nd){
					comp.pb(S.top());
					S.pop();
				}
				comp.pb(e.nd);
				S.pop();
				G.pb(comp);
			}
		}
	}
	if(p == -1 && c > 1){
		art.pb(u);
	}
}

void decompose(){
	fr(i, 0, n){
		if(vis[i]) continue;
		dfs(i, -1);
		vector<int> lst;
		while(!S.empty()){
			lst.pb(S.top());
			S.pop();
		}
		G.pb(lst);
	}
	sort(all(art));
	art.erase(unique(all(art)), art.end());
}

vector<pii> edge;

set<int> inter[mxn];

ll sz[mxn];


vector<int> tree[mxn];
ll totsum = 0;

ll cs(int u, int p){
	ll ret = sz[u];
	for(auto e : tree[u]){
		if(e == p) continue;
		ret += cs(e, u);
	}
	return ret;
}


int build_tree(){
	int id = 0;
	for(auto u : G){
		set<int> ver;
		for(auto e : u){
			int a = edge[e].st;
			int b = edge[e].nd;
			inter[a].insert(id);
			inter[b].insert(id);
			ver.insert(a);
			ver.insert(b);
		}
		
		sz[id] = (int)ver.size();
		++id;
	}
	for(auto a : art){
		sz[id] = 1;
		for(auto u : inter[a]){
			--sz[u];
			
			artin[u] ++;
			tree[id].pb(u);
			tree[u].pb(id);
		}
		++id;
	}
	return id;
}

ll sub[mxn];
ll ans = 0;


void dfst(int u){
	vis[u] = true;
	sub[u] = sz[u];
	
	vector<ll> V;
	
	for(auto e : tree[u]){
		if(vis[e]) continue;
		dfst(e);
		sub[u] += sub[e];
		V.pb(sub[e]);
	}
	V.pb(totsum-sub[u]);
	
	ll s = totsum - sz[u];
	
	ans += s*s*sz[u];
	for(auto e : V) ans -= e*e*sz[u];
	
	ll S = artin[u] + sz[u];
	
	if(S >= 3){
		ans += S*(S-1)*(S-2);
	}
	
	if(sz[u] >= 2){
		ans += (sz[u]*(sz[u]-1))*(s-artin[u])*2;
	}
}
	
void solve_tree(int k){
	memset(vis, false, sizeof(vis));
	fr(i, 0, k){
		if(vis[i]) continue;
		totsum = cs(i, i);
		dfst(i);
	}
}
void solve(){
	cin >> n >> m;
	fr(i, 0, m){
		int u, v;
		cin >> u >> v;
		--u, --v;
		
		g[u].pb({v, i});
		g[v].pb({u, i});
		edge.pb({u, v});
	}
	decompose();
	
	int k = build_tree();	
	
	solve_tree(k);
	
	cout<<ans<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}
/*
10 8
1 2
1 3
3 4
3 5
6 7
6 8
8 9
8 10
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47756 KB Output is correct
2 Correct 25 ms 47772 KB Output is correct
3 Correct 26 ms 47796 KB Output is correct
4 Correct 25 ms 47684 KB Output is correct
5 Correct 26 ms 47692 KB Output is correct
6 Correct 24 ms 47812 KB Output is correct
7 Incorrect 25 ms 47820 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47756 KB Output is correct
2 Correct 25 ms 47772 KB Output is correct
3 Correct 26 ms 47796 KB Output is correct
4 Correct 25 ms 47684 KB Output is correct
5 Correct 26 ms 47692 KB Output is correct
6 Correct 24 ms 47812 KB Output is correct
7 Incorrect 25 ms 47820 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 191 ms 78528 KB Output is correct
2 Correct 184 ms 78388 KB Output is correct
3 Correct 223 ms 80428 KB Output is correct
4 Correct 232 ms 78072 KB Output is correct
5 Correct 241 ms 74048 KB Output is correct
6 Correct 229 ms 84404 KB Output is correct
7 Correct 262 ms 76612 KB Output is correct
8 Correct 245 ms 80632 KB Output is correct
9 Correct 215 ms 73652 KB Output is correct
10 Correct 205 ms 73344 KB Output is correct
11 Correct 144 ms 65724 KB Output is correct
12 Correct 138 ms 65676 KB Output is correct
13 Correct 124 ms 64376 KB Output is correct
14 Correct 122 ms 64308 KB Output is correct
15 Correct 96 ms 61612 KB Output is correct
16 Correct 100 ms 61652 KB Output is correct
17 Correct 36 ms 52672 KB Output is correct
18 Correct 36 ms 52664 KB Output is correct
19 Correct 36 ms 52684 KB Output is correct
20 Correct 35 ms 52592 KB Output is correct
21 Correct 35 ms 52556 KB Output is correct
22 Correct 35 ms 52564 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 48156 KB Output is correct
2 Correct 27 ms 48076 KB Output is correct
3 Correct 27 ms 48076 KB Output is correct
4 Correct 28 ms 48360 KB Output is correct
5 Correct 28 ms 48200 KB Output is correct
6 Correct 27 ms 48204 KB Output is correct
7 Correct 27 ms 48256 KB Output is correct
8 Correct 27 ms 48204 KB Output is correct
9 Correct 27 ms 48204 KB Output is correct
10 Correct 27 ms 48096 KB Output is correct
11 Correct 27 ms 48076 KB Output is correct
12 Correct 27 ms 48100 KB Output is correct
13 Correct 27 ms 48008 KB Output is correct
14 Correct 28 ms 48088 KB Output is correct
15 Correct 27 ms 47980 KB Output is correct
16 Correct 26 ms 47948 KB Output is correct
17 Correct 27 ms 48088 KB Output is correct
18 Correct 26 ms 47968 KB Output is correct
19 Correct 27 ms 48104 KB Output is correct
20 Correct 27 ms 48068 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 76420 KB Output is correct
2 Correct 263 ms 76428 KB Output is correct
3 Correct 233 ms 76440 KB Output is correct
4 Correct 243 ms 76336 KB Output is correct
5 Correct 235 ms 76388 KB Output is correct
6 Correct 320 ms 103072 KB Output is correct
7 Correct 290 ms 86612 KB Output is correct
8 Correct 283 ms 84144 KB Output is correct
9 Correct 289 ms 81608 KB Output is correct
10 Correct 244 ms 76384 KB Output is correct
11 Correct 235 ms 77700 KB Output is correct
12 Correct 233 ms 77612 KB Output is correct
13 Correct 230 ms 77648 KB Output is correct
14 Correct 203 ms 74932 KB Output is correct
15 Correct 182 ms 72172 KB Output is correct
16 Correct 114 ms 64048 KB Output is correct
17 Correct 163 ms 77620 KB Output is correct
18 Correct 164 ms 77112 KB Output is correct
19 Correct 167 ms 77144 KB Output is correct
20 Correct 161 ms 76712 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 48076 KB Output is correct
2 Correct 27 ms 48028 KB Output is correct
3 Incorrect 28 ms 48024 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 76420 KB Output is correct
2 Correct 254 ms 76796 KB Output is correct
3 Incorrect 260 ms 74320 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47756 KB Output is correct
2 Correct 25 ms 47772 KB Output is correct
3 Correct 26 ms 47796 KB Output is correct
4 Correct 25 ms 47684 KB Output is correct
5 Correct 26 ms 47692 KB Output is correct
6 Correct 24 ms 47812 KB Output is correct
7 Incorrect 25 ms 47820 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47756 KB Output is correct
2 Correct 25 ms 47772 KB Output is correct
3 Correct 26 ms 47796 KB Output is correct
4 Correct 25 ms 47684 KB Output is correct
5 Correct 26 ms 47692 KB Output is correct
6 Correct 24 ms 47812 KB Output is correct
7 Incorrect 25 ms 47820 KB Output isn't correct
8 Halted 0 ms 0 KB -