oj.uz

Submission #413736

# Submission time Handle Problem Language Result Execution time Memory
413736 2021-05-29T09:44:27 Z hhhhaura Duathlon (APIO18_duathlon) C++14
0 / 100
 245 ms 64476 KB 
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i ,a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))

#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)

using namespace std;
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().times_since_epoch().count())

#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
namespace solver {
	int n, ans = 0 ;
	vector<vector<int>> mp;
	vector<int> dp1, sz, w, vis;
	void init_(int _n, vector<vector<int>> _mp, vector<int> _w) {
		n = _n, ans = 0;
		dp1.assign(n + 1, 0);
		sz.assign(n + 1, 0);
		vis.assign(n + 1, 0);
		w = _w, mp = _mp;
//		assert(w.size() == n + 1&& mp.size() == n + 1);
	}
	void dfs(int x, int par) {
		vis[x] = 1, sz[x] = w[x], dp1[x] = 0;
		for(auto i : mp[x]) if(i != par) {
			dfs(i, x); 
			dp1[x] += dp1[i] + bool(w[x]) * sz[i];
			sz[x] += sz[i];
		}
		int temp = 0, cur = 0;
		for(auto i : mp[x]) if(i != par) {
			temp +=  dp1[i] * (sz[x] - sz[i]);
			temp += cur * sz[i];
			cur += sz[i];
		}
		if(w[x]) ans += temp;
		return;
	}
};
namespace solver1 {
	int n, m, ii, timestamp, bccid;
	vector<int> es, x, y, ide, idv, sz;
	vector<int> L, D, pre, iscut;
	vector<vector<int>> mp1, mp2;
	void init_(int _n, int _m) {
		n = _n, m = _m;
		ii = 0, timestamp = 0, bccid = 0;
		es.assign(m + 1, 0);
		sz.assign(2 * n + 1, 0);
		x.assign(m + 1, 0);
		y.assign(m + 1, 0);
		ide.assign(m + 1, 0);
		idv.assign(n + 1, 0);
		L.assign(n + 1, 0);
		D.assign(n + 1, 0);
		pre.assign(m + 1, 0);
		iscut.assign(n + 1, 0);
		mp1.assign(n + 1, vector<int>());
		mp2.assign(2 * n + 1, vector<int>());
	}
	void add_edge(int u, int v, int id) {
		x[id] = u, y[id] = v;
		es[id] = u ^ v;
		mp1[u].push_back(id);
		mp1[v].push_back(id);
	}
	void dfs(int x, int par) {
		D[x] = L[x] = ++ timestamp;
		int cnt = 0, isAP = 0;
		for(auto i : mp1[x]) if(i != par) {
			int to = es[i] ^ x;
			if(!D[to]) {
				pre[ii ++] = i;
				cnt ++, dfs(to, i);
				L[x] = min(L[x], L[to]);
				if(L[to] >= D[x]) {
					isAP = 1, bccid ++;
					while(pre[ii] != i) {
						ii --, ide[pre[ii]] = bccid;
					}
				}
			}
			else if(D[to] < D[x]) {
				pre[ii ++] = i;
				L[x] = min(L[x], D[to]);
			}
		}
		if(par == -1 && cnt < 2) isAP = 0;
		iscut[x] = isAP;
		return;
	}
	int solve() {
		rep(i, 1, n) if(!D[i]) dfs(i, -1);
		rep(i, 1, n) if(iscut[i]) idv[i] = ++bccid;
//		assert(bccid <= 2 * n);
		rep(i, 1, m) {
			if(!iscut[x[i]]) idv[x[i]] = ide[i];
			else {
				mp2[idv[x[i]]].push_back(ide[i]);
				mp2[ide[i]].push_back(idv[x[i]]);
			}
			if(!iscut[y[i]]) idv[y[i]] = ide[i];
			else {
				mp2[idv[y[i]]].push_back(ide[i]);
				mp2[ide[i]].push_back(idv[y[i]]);
			}
		}
		rep(i, 1, n) sz[idv[i]] ++;
		rep(i, 1, 2 * n) {
			sort(all(mp2[i]));
			mp2[i].resize(unique(all(mp2[i])) - mp2[i].begin());
		}
		solver::init_(2 * n, mp2, sz);
		int ans = 0, cnt = 0;
		rep(i, 1, 2 * n) if(!solver::vis[i]) solver::dfs(i, i);
		rep(i, 1, 2 * n) if(sz[i]) cnt ++;
		rep(i, 1, 2 * n) {
			ans += sz[i] * (sz[i] - 1) * (sz[i] - 2) / 2;
			ans += sz[i] * (sz[i] - 1) * (cnt - 1);
		}
		rep(i, 1, n) if(iscut[i]) {
			for(auto j : mp2[idv[i]]) ans += sz[j] * (sz[j] - 1) / 2;
		}
		ans += solver::ans;
		return ans * 2;
	}
}
using namespace solver1;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m; cin >> n >> m;
	init_(n, m);
	rep(i, 1, m) {
		int a, b; cin >> a >> b;
		add_edge(a, b, i);
	}
	cout << solve() << "\n";
	return 0;
}

Compilation message

count_triplets.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
count_triplets.cpp:23:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
count_triplets.cpp:23:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |                     ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Incorrect 1 ms 320 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Incorrect 1 ms 320 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 45656 KB Output is correct
2 Correct 96 ms 45636 KB Output is correct
3 Incorrect 161 ms 50432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 2 ms 972 KB Output is correct
5 Correct 2 ms 844 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 2 ms 984 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 2 ms 716 KB Output is correct
14 Incorrect 2 ms 716 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 52120 KB Output is correct
2 Correct 179 ms 52168 KB Output is correct
3 Correct 185 ms 52152 KB Output is correct
4 Correct 192 ms 52160 KB Output is correct
5 Correct 180 ms 52164 KB Output is correct
6 Correct 245 ms 64476 KB Output is correct
7 Correct 213 ms 56916 KB Output is correct
8 Correct 218 ms 55724 KB Output is correct
9 Correct 218 ms 54688 KB Output is correct
10 Correct 176 ms 52076 KB Output is correct
11 Correct 175 ms 52140 KB Output is correct
12 Correct 173 ms 52148 KB Output is correct
13 Correct 176 ms 52152 KB Output is correct
14 Incorrect 195 ms 49760 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 52112 KB Output is correct
2 Correct 196 ms 52752 KB Output is correct
3 Incorrect 214 ms 51684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Incorrect 1 ms 320 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Incorrect 1 ms 320 KB Output isn't correct
8 Halted 0 ms 0 KB -