oj.uz

Submission #413732

# Submission time Handle Problem Language Result Execution time Memory
413732 2021-05-29T09:42:10 Z hhhhaura Duathlon (APIO18_duathlon) C++14
0 / 100
 243 ms 64464 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(n + 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 Runtime error 1 ms 460 KB Execution killed with signal 11
3 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 Runtime error 1 ms 460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 45624 KB Output is correct
2 Correct 97 ms 45724 KB Output is correct
3 Incorrect 145 ms 50420 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 972 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 173 ms 52132 KB Output is correct
2 Correct 216 ms 52120 KB Output is correct
3 Correct 176 ms 52080 KB Output is correct
4 Correct 175 ms 52164 KB Output is correct
5 Correct 177 ms 52112 KB Output is correct
6 Correct 243 ms 64464 KB Output is correct
7 Correct 218 ms 56968 KB Output is correct
8 Correct 209 ms 55748 KB Output is correct
9 Correct 205 ms 54680 KB Output is correct
10 Correct 177 ms 52104 KB Output is correct
11 Correct 178 ms 52108 KB Output is correct
12 Correct 172 ms 52164 KB Output is correct
13 Correct 176 ms 52160 KB Output is correct
14 Incorrect 160 ms 49860 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 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 186 ms 52072 KB Output is correct
2 Correct 198 ms 52712 KB Output is correct
3 Incorrect 198 ms 51564 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 Runtime error 1 ms 460 KB Execution killed with signal 11
3 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 Runtime error 1 ms 460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -