oj.uz

Submission #421230

# Submission time Handle Problem Language Result Execution time Memory
421230 2021-06-08T22:23:59 Z Blagojce Duathlon (APIO18_duathlon) C++11
0 / 100
 317 ms 103028 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);
	
	if(ans < 0) cout<<2/0<<endl;
	cout<<ans<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

Compilation message

count_triplets.cpp: In function 'void solve()':
count_triplets.cpp:197:21: warning: division by zero [-Wdiv-by-zero]
  197 |  if(ans < 0) cout<<2/0<<endl;
      |                    ~^~

Subtask #1
0 / 5.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 78448 KB Output is correct
2 Correct 193 ms 78372 KB Output is correct
3 Incorrect 221 ms 80472 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 48056 KB Output is correct
3 Correct 31 ms 48076 KB Output is correct
4 Correct 29 ms 48300 KB Output is correct
5 Correct 28 ms 48204 KB Output is correct
6 Correct 27 ms 48196 KB Output is correct
7 Correct 28 ms 48280 KB Output is correct
8 Correct 27 ms 48092 KB Output is correct
9 Correct 28 ms 48056 KB Output is correct
10 Incorrect 28 ms 48076 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 76336 KB Output is correct
2 Correct 239 ms 76432 KB Output is correct
3 Correct 236 ms 76328 KB Output is correct
4 Correct 230 ms 76360 KB Output is correct
5 Correct 254 ms 76356 KB Output is correct
6 Correct 314 ms 103028 KB Output is correct
7 Correct 317 ms 86568 KB Output is correct
8 Correct 294 ms 84116 KB Output is correct
9 Correct 303 ms 81592 KB Output is correct
10 Incorrect 261 ms 76396 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48068 KB Output is correct
2 Correct 30 ms 48056 KB Output is correct
3 Incorrect 34 ms 48076 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 76340 KB Output is correct
2 Correct 272 ms 76752 KB Output is correct
3 Incorrect 287 ms 74128 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 47820 KB Output is correct
2 Correct 26 ms 47700 KB Output is correct
3 Correct 26 ms 47820 KB Output is correct
4 Correct 26 ms 47768 KB Output is correct
5 Correct 27 ms 47820 KB Output is correct
6 Correct 28 ms 47776 KB Output is correct
7 Incorrect 28 ms 47812 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 47700 KB Output is correct
3 Correct 26 ms 47820 KB Output is correct
4 Correct 26 ms 47768 KB Output is correct
5 Correct 27 ms 47820 KB Output is correct
6 Correct 28 ms 47776 KB Output is correct
7 Incorrect 28 ms 47812 KB Output isn't correct
8 Halted 0 ms 0 KB -