oj.uz

Submission #421229

# Submission time Handle Problem Language Result Execution time Memory
421229 2021-06-08T22:21:55 Z Blagojce Duathlon (APIO18_duathlon) C++11
0 / 100
 304 ms 104312 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;

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 47776 KB Output is correct
2 Correct 26 ms 47720 KB Output is correct
3 Correct 26 ms 47776 KB Output is correct
4 Correct 26 ms 47768 KB Output is correct
5 Correct 26 ms 47692 KB Output is correct
6 Correct 26 ms 47776 KB Output is correct
7 Incorrect 26 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 26 ms 47776 KB Output is correct
2 Correct 26 ms 47720 KB Output is correct
3 Correct 26 ms 47776 KB Output is correct
4 Correct 26 ms 47768 KB Output is correct
5 Correct 26 ms 47692 KB Output is correct
6 Correct 26 ms 47776 KB Output is correct
7 Incorrect 26 ms 47820 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 78664 KB Output is correct
2 Correct 212 ms 78432 KB Output is correct
3 Incorrect 230 ms 80440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 48076 KB Output is correct
2 Correct 28 ms 48208 KB Output is correct
3 Correct 28 ms 48108 KB Output is correct
4 Correct 28 ms 48332 KB Output is correct
5 Correct 28 ms 48224 KB Output is correct
6 Correct 27 ms 48160 KB Output is correct
7 Correct 28 ms 48340 KB Output is correct
8 Correct 28 ms 48144 KB Output is correct
9 Correct 27 ms 48084 KB Output is correct
10 Incorrect 27 ms 48036 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 76340 KB Output is correct
2 Correct 292 ms 77632 KB Output is correct
3 Correct 279 ms 77844 KB Output is correct
4 Correct 276 ms 77608 KB Output is correct
5 Correct 303 ms 77620 KB Output is correct
6 Correct 299 ms 104312 KB Output is correct
7 Correct 287 ms 87848 KB Output is correct
8 Correct 304 ms 85312 KB Output is correct
9 Correct 283 ms 82888 KB Output is correct
10 Incorrect 278 ms 77616 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 48068 KB Output is correct
2 Correct 27 ms 48084 KB Output is correct
3 Incorrect 27 ms 48012 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 76376 KB Output is correct
2 Correct 279 ms 78000 KB Output is correct
3 Incorrect 277 ms 75728 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 47776 KB Output is correct
2 Correct 26 ms 47720 KB Output is correct
3 Correct 26 ms 47776 KB Output is correct
4 Correct 26 ms 47768 KB Output is correct
5 Correct 26 ms 47692 KB Output is correct
6 Correct 26 ms 47776 KB Output is correct
7 Incorrect 26 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 26 ms 47776 KB Output is correct
2 Correct 26 ms 47720 KB Output is correct
3 Correct 26 ms 47776 KB Output is correct
4 Correct 26 ms 47768 KB Output is correct
5 Correct 26 ms 47692 KB Output is correct
6 Correct 26 ms 47776 KB Output is correct
7 Incorrect 26 ms 47820 KB Output isn't correct
8 Halted 0 ms 0 KB -