oj.uz

Submission #421220

# Submission time Handle Problem Language Result Execution time Memory
421220 2021-06-08T21:52:54 Z Blagojce Duathlon (APIO18_duathlon) C++11
0 / 100
 239 ms 79784 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];

int 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);
	}
}

vector<pii> edge;

set<int> inter[mxn];

int sz[mxn];


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

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;
	}
	fr(i, 0, id) totsum += sz[i];
	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;
		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();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47820 KB Output is correct
2 Correct 26 ms 47792 KB Output is correct
3 Correct 26 ms 47780 KB Output is correct
4 Correct 27 ms 47768 KB Output is correct
5 Correct 26 ms 47708 KB Output is correct
6 Correct 27 ms 47920 KB Output is correct
7 Incorrect 26 ms 47824 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47820 KB Output is correct
2 Correct 26 ms 47792 KB Output is correct
3 Correct 26 ms 47780 KB Output is correct
4 Correct 27 ms 47768 KB Output is correct
5 Correct 26 ms 47708 KB Output is correct
6 Correct 27 ms 47920 KB Output is correct
7 Incorrect 26 ms 47824 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 78456 KB Output is correct
2 Correct 177 ms 78464 KB Output is correct
3 Incorrect 188 ms 79784 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47820 KB Output is correct
2 Correct 26 ms 47792 KB Output is correct
3 Correct 26 ms 47780 KB Output is correct
4 Correct 27 ms 47768 KB Output is correct
5 Correct 26 ms 47708 KB Output is correct
6 Correct 27 ms 47920 KB Output is correct
7 Incorrect 26 ms 47824 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47820 KB Output is correct
2 Correct 26 ms 47792 KB Output is correct
3 Correct 26 ms 47780 KB Output is correct
4 Correct 27 ms 47768 KB Output is correct
5 Correct 26 ms 47708 KB Output is correct
6 Correct 27 ms 47920 KB Output is correct
7 Incorrect 26 ms 47824 KB Output isn't correct
8 Halted 0 ms 0 KB -