oj.uz

Submission #252448

# Submission time Handle Problem Language Result Execution time Memory
252448 2020-07-25T15:30:43 Z amoo_safar Duathlon (APIO18_duathlon) C++14
23 / 100
 466 ms 174288 KB 
#include<bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define debug(x) cerr << #x << " = " << x << '\n'
#define int ll
using namespace std;

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

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

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;
	}
	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];

int32_t 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 += 1ll * (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 - (1ll * 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 'int32_t main()':
count_triplets.cpp:184:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [tm, adj] : ed) S2 += 1ll * (tm) * (tm - 1); 
              ^
count_triplets.cpp:184:22: warning: unused variable 'adj' [-Wunused-variable]
     for(auto [tm, adj] : ed) S2 += 1ll * (tm) * (tm - 1); 
                      ^
count_triplets.cpp:186:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [tm, adj] : ed){
              ^
count_triplets.cpp:200:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for(auto [res, fl] : oth){
             ^
count_triplets.cpp:200:21: warning: unused variable 'fl' [-Wunused-variable]
    for(auto [res, fl] : oth){
                     ^
count_triplets.cpp:204:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for(auto [res, fl] : oth){
             ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 107384 KB Output is correct
2 Correct 63 ms 107364 KB Output is correct
3 Correct 61 ms 107384 KB Output is correct
4 Correct 60 ms 107512 KB Output is correct
5 Correct 62 ms 107512 KB Output is correct
6 Correct 60 ms 107512 KB Output is correct
7 Correct 67 ms 107768 KB Output is correct
8 Correct 61 ms 107384 KB Output is correct
9 Correct 61 ms 107384 KB Output is correct
10 Correct 61 ms 107384 KB Output is correct
11 Correct 63 ms 107384 KB Output is correct
12 Correct 61 ms 107384 KB Output is correct
13 Correct 65 ms 107476 KB Output is correct
14 Correct 61 ms 107256 KB Output is correct
15 Correct 61 ms 107260 KB Output is correct
16 Correct 62 ms 107128 KB Output is correct
17 Correct 62 ms 107384 KB Output is correct
18 Correct 66 ms 107512 KB Output is correct
19 Correct 71 ms 107384 KB Output is correct
20 Correct 69 ms 107384 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 158164 KB Output is correct
2 Correct 419 ms 158164 KB Output is correct
3 Correct 425 ms 158164 KB Output is correct
4 Correct 407 ms 158164 KB Output is correct
5 Correct 414 ms 158292 KB Output is correct
6 Correct 430 ms 174288 KB Output is correct
7 Correct 466 ms 169552 KB Output is correct
8 Correct 451 ms 166508 KB Output is correct
9 Correct 453 ms 163668 KB Output is correct
10 Correct 435 ms 156756 KB Output is correct
11 Correct 418 ms 158036 KB Output is correct
12 Correct 418 ms 156244 KB Output is correct
13 Correct 430 ms 156028 KB Output is correct
14 Correct 389 ms 151892 KB Output is correct
15 Correct 337 ms 148316 KB Output is correct
16 Correct 223 ms 136800 KB Output is correct
17 Correct 363 ms 160432 KB Output is correct
18 Correct 350 ms 158764 KB Output is correct
19 Correct 363 ms 159724 KB Output is correct
20 Correct 361 ms 158988 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 107512 KB Output is correct
2 Correct 61 ms 107384 KB Output is correct
3 Incorrect 60 ms 107256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 158228 KB Output is correct
2 Correct 435 ms 157800 KB Output is correct
3 Incorrect 411 ms 154716 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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