oj.uz

Submission #252444

# Submission time Handle Problem Language Result Execution time Memory
252444 2020-07-25T15:25:51 Z amoo_safar Duathlon (APIO18_duathlon) C++17
0 / 100
 409 ms 226800 KB 
#include<bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define debug(x) cerr << #x << " = " << x << '\n'

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 10;
const int N2 = N * 8;

ll ans;
int n, m;

int la;
vector<int> H[N], G[N2], R[N2];

int mk[N2], st[N], T = 1, dep[N2], wh[N];

void AddEdge(int u, int v){
	G[u].pb(v);
	G[v].pb(u);
	//cerr << u << ' ' << v << '\n';
}

int dfs(int u, int p, int d){
	mk[u] = 1;
	dep[u] = d;
	st[u] = T ++;

	int hbk = d, res;
	int cnt = (p == -1 ? 0 : 1);
	
	vector<pii> V;

	for(auto adj : H[u]){
		if(adj == p) continue;
		if(mk[adj]){
			hbk = min(hbk, dep[adj]);
		} else {
			res = dfs(adj, u, d + 1);
			hbk = min(hbk, res);
			if(res >= d){
				cnt ++;
				V.pb({T, cnt});
			} else {
				V.pb({T, 1});
			}

		}
	}
	//cerr << "! " << u << ' ' << cnt << ' ' << la << '\n';
	if(cnt > 0){
		wh[u] = la + 1;
		for(int i = 1; i <= cnt; i++) AddEdge(u, la + i);
		int idx;
		for(auto adj : H[u]){
			if(dep[adj] < dep[u]) idx = 1;
			else idx = upper_bound(V.begin(), V.end(), pii(st[adj], cnt + 1)) -> S;
			if(dep[adj] >= dep[u]) AddEdge(wh[adj], la + idx);
		}
		la += cnt;
	} else {
		assert(0);
	}
	return hbk;
}

int par[N2], sz[N];
int Find(int u){
	if(par[u] == u) return u;
	return par[u] = Find(par[u]);
}
void Unite(int u, int v){
	u = Find(u); v = Find(v);
	if(u == v) return ;
	par[u] = v;
	sz[v] += sz[u];
}

vector<pii> cut;
int DFS(int u, int p, int d){
	mk[u] = 1;
	dep[u] = d;

	int hbk = d, res;
	for(auto adj : G[u]){
		if(adj == p) continue;
		if(mk[adj]){
			hbk = min(hbk, dep[adj]);
			Unite(u, adj);
		} else {
			res = DFS(adj, u, d + 1);
			hbk = min(res, hbk);
			if(res <= d) Unite(adj, u);
			else {
				cut.pb(pii(adj, u));
			}
		}
	}
	return hbk;
}
int sub[N2];
vector<int> vis;
vector<pii> oth;
void DFS2(int u, int p, int d){
	vis.pb(u);
	sub[u] = sz[u];
	dep[u] = d;
	mk[u] = 1;
	for(auto adj : R[u]){
		if(adj == p) continue;
		DFS2(adj, u, d + 1);
		sub[u] += sub[adj];
	}
}

vector<int> com[N2];
vector<int> fuck[N2];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	int u, v;
	for(int i = 1; i <= m; i++){
		cin >> u >> v;
		H[u].pb(v);
		H[v].pb(u);
	}

	cerr << '\n';
	
	la = n;
	for(int i = 1; i <= n; i++){
		if(mk[i]) continue;
		dfs(i, -1, 0);
	}
	iota(par, par + N2, 0);
	fill(sz + 1, sz + n + 1, 1);

	memset(mk, 0, sizeof mk);
	for(int i = 1; i <= la; i++){
		if(mk[i]) continue;
		DFS(i, -1, 0);
	}
	for(int i = 1; i <= la; i++) com[Find(i)].pb(i);

	for(auto &x : cut){
		x.F = Find(x.F); x.S = Find(x.S);
		R[x.F].pb(x.S);
		R[x.S].pb(x.F);
	}

	memset(mk, 0, sizeof mk);
	
	for(int i = 1; i <= la; i++){
		if(mk[i]) continue;
		if(Find(i) != i) continue;
		vis.clear();
		DFS2(i, -1, 0);


		int sm = sub[i];
		for(auto nd : vis){
			oth.clear();
			vector<int> con;
			for(auto nd2 : com[nd]){
				int res = (nd2 <= n), res2 = 0, tmp;
				
				vector<pii> ed;
				for(auto adj : G[nd2]){
					if(Find(adj) == nd) continue;
					int tm;
					tmp = Find(adj);
					if(dep[tmp] > dep[nd]) tm = sub[tmp];
					else tm = sm - sub[nd];
					ed.pb({tm, adj});
					res += tm;
					res2 += tm;
				}
				ll S2 = 0;
				for(auto [tm, adj] : ed) S2 += (tm) * (tm - 1); 
				bool fl = false;
				for(auto [tm, adj] : ed){
					if((adj <= n) && (wh[adj] != adj)){
						fuck[adj].pb(sm - tm);
						//if(nd2 <= n) tm --;
						ans += 1ll * (res2 - tm) * (res2 - tm - 1);
						ans -= S2 - (tm * (tm - 1));

						ans += 2ll * (sm - res) * (res2 - tm);
						fl = true;
					}
				}
				oth.pb({res, fl});
			}
			ll Sum = 0, S2 = 0;
			for(auto [res, fl] : oth){
				Sum += res;
				S2 += res * (res - 1);
			}
			for(auto [res, fl] : oth){
				if(fl){
					ans += 1ll * (Sum - res) * (Sum - res - 1);
					ans -= S2 - (1ll * (res) * (res - 1));
				}
			}
				
		}
	}
	ans = 0;
	for(int i = 1; i <= n; i++){
		if(wh[i] == i) continue;

		int sm = 0;
		for(auto x : fuck[i]){
			sm += x;
			ans -= 1ll * x * (x - 1);
		}
		ans += 1ll * sm * (sm - 1);
	}
	cout << ans << '\n';
	return 0;
}
/*
9 10
1 2
2 3
3 4
4 5
4 2
3 6
6 7
6 8
8 3
8 9


10 9
1 2
2 3
*/

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:186:22: warning: unused variable 'adj' [-Wunused-variable]
     for(auto [tm, adj] : ed) S2 += (tm) * (tm - 1); 
                      ^
count_triplets.cpp:202:21: warning: unused variable 'fl' [-Wunused-variable]
    for(auto [res, fl] : oth){
                     ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 157560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 157560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 314 ms 226800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 84600 KB Output is correct
2 Correct 57 ms 84600 KB Output is correct
3 Correct 52 ms 84592 KB Output is correct
4 Correct 51 ms 84728 KB Output is correct
5 Correct 56 ms 84716 KB Output is correct
6 Correct 62 ms 84728 KB Output is correct
7 Correct 52 ms 84728 KB Output is correct
8 Correct 70 ms 84600 KB Output is correct
9 Correct 50 ms 84600 KB Output is correct
10 Correct 61 ms 84600 KB Output is correct
11 Correct 51 ms 84600 KB Output is correct
12 Correct 71 ms 84604 KB Output is correct
13 Correct 50 ms 84604 KB Output is correct
14 Runtime error 126 ms 157816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 84600 KB Output is correct
2 Correct 56 ms 84600 KB Output is correct
3 Incorrect 51 ms 84472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 157560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 146 ms 157560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -