oj.uz

Submission #316513

# Submission time Handle Problem Language Result Execution time Memory
316513 2020-10-26T13:47:31 Z Kevin_Zhang_TW Duathlon (APIO18_duathlon) C++17
31 / 100
 186 ms 47656 KB 
#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() {cerr << endl;}
template<class T1, class ...T2>
void kout (T1 v, T2 ...e) { cerr << v << ' ', kout(e...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L)==R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010;
int n, m, low[MAX_N], dep[MAX_N], g[MAX_N], bcc, sz[MAX_N], dfscnt;
vector<int> edge[MAX_N], be[MAX_N], child[MAX_N];
bool isap[MAX_N];
void dfs1(int x, int lst = -1) {
	++dfscnt;
	static stack<int> st;
	static int d;
	st.push(x);
	low[x] = dep[x] = ++d;
	for (int u : edge[x]) if (u != lst) {
		DE(x, u);
		if (!low[u]) {
			dfs1(u, x);
			low[x] = min(low[x], low[u]);
			if (low[u] >= dep[x]) {
				isap[x] = true;
				st.push(x);
				int gid = ++bcc + n;
				int tp = -1; do {
					tp = st.top(); st.pop();
					g[tp] = gid;
					child[gid].pb(tp);
					if (isap[tp]) {
						be[gid].pb(tp), be[tp].pb(gid);
						DE(tp, gid);
					}
				} while (tp != u);
			}
		}
		else low[x] = min(low[x], dep[u]);
	}
}
ll p2(ll v) { return v * (v-1); }
// count how many invalid triple there is
ll dfs2(int x, int m, int lst = -1) {
	ll res = 0;
	sz[x] = x <= n ? 1 : child[x].size();
	for (int u : be[x]) if (u != lst)
		res += dfs2(u, m, x), sz[x] += sz[u] - 1;
DE(x, sz[x]);

	if (x <= n) {
		ll all = p2(m-1);
		// way is the number of valid triples
		ll sum = m - sz[x], way = 0;
		for (int u : be[x]) if (u != lst) {
			way += (sz[u]-1) * sum * 2;
			sum += (sz[u]-1);
			ll cs = child[u].size() - 1;
			way += p2(cs);
		}
		if (lst != -1)
			way += p2(child[lst].size()-1);

		//DE(x, all, way);
		res += all - way;
	}
	else {
		ll mid = 0, upsz = m - sz[x] + 1;
		for (int u : child[x])
			if (!isap[u]) ++mid;
		for (int u : be[x]) if (u != lst) {
			res += p2(sz[u]) * mid;
		}
		res += p2(upsz) * mid;
	}
	DE(res);
	return res;
}
ll cal(int s) {
	dfscnt = 0;
	dfs1(s);
	ll m = dfscnt;
	return (m * (m-1) * (m-2)) - dfs2(s, m);
	//return 0;
}
signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 0, a, b;i < m;++i) {
		cin >> a >> b;
		edge[a].pb(b);
		edge[b].pb(a);
	}
	ll res = 0;
	for (int i = 1;i <= n;++i) 
		if (!dep[i])
			res += cal(i);
	cout << res << '\n';

}

Compilation message

count_triplets.cpp: In function 'void dfs1(int, int)':
count_triplets.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
count_triplets.cpp:28:3: note: in expansion of macro 'DE'
   28 |   DE(x, u);
      |   ^~
count_triplets.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
count_triplets.cpp:42:7: note: in expansion of macro 'DE'
   42 |       DE(tp, gid);
      |       ^~
count_triplets.cpp: In function 'll dfs2(int, int, int)':
count_triplets.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
count_triplets.cpp:57:1: note: in expansion of macro 'DE'
   57 | DE(x, sz[x]);
      | ^~
count_triplets.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
count_triplets.cpp:84:2: note: in expansion of macro 'DE'
   84 |  DE(res);
      |  ^~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 35776 KB Output is correct
2 Correct 92 ms 35760 KB Output is correct
3 Correct 143 ms 40388 KB Output is correct
4 Correct 113 ms 36864 KB Output is correct
5 Correct 115 ms 36040 KB Output is correct
6 Correct 144 ms 39544 KB Output is correct
7 Correct 146 ms 37496 KB Output is correct
8 Correct 152 ms 38136 KB Output is correct
9 Correct 141 ms 35448 KB Output is correct
10 Correct 125 ms 35316 KB Output is correct
11 Correct 106 ms 32376 KB Output is correct
12 Correct 106 ms 31992 KB Output is correct
13 Correct 95 ms 31864 KB Output is correct
14 Correct 109 ms 31480 KB Output is correct
15 Correct 78 ms 30584 KB Output is correct
16 Correct 77 ms 30328 KB Output is correct
17 Correct 18 ms 23552 KB Output is correct
18 Correct 18 ms 23552 KB Output is correct
19 Correct 18 ms 23552 KB Output is correct
20 Correct 18 ms 23552 KB Output is correct
21 Correct 19 ms 23552 KB Output is correct
22 Correct 18 ms 23552 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 21632 KB Output is correct
2 Correct 16 ms 21632 KB Output is correct
3 Correct 18 ms 21632 KB Output is correct
4 Correct 16 ms 21760 KB Output is correct
5 Correct 16 ms 21760 KB Output is correct
6 Correct 16 ms 21760 KB Output is correct
7 Correct 16 ms 21760 KB Output is correct
8 Correct 16 ms 21760 KB Output is correct
9 Correct 16 ms 21632 KB Output is correct
10 Correct 16 ms 21632 KB Output is correct
11 Correct 16 ms 21632 KB Output is correct
12 Correct 16 ms 21632 KB Output is correct
13 Correct 16 ms 21632 KB Output is correct
14 Correct 21 ms 21624 KB Output is correct
15 Correct 16 ms 21632 KB Output is correct
16 Correct 21 ms 21624 KB Output is correct
17 Correct 16 ms 21632 KB Output is correct
18 Correct 19 ms 21624 KB Output is correct
19 Correct 16 ms 21632 KB Output is correct
20 Correct 19 ms 21632 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 35960 KB Output is correct
2 Correct 153 ms 35964 KB Output is correct
3 Correct 160 ms 35960 KB Output is correct
4 Correct 165 ms 35960 KB Output is correct
5 Correct 154 ms 36012 KB Output is correct
6 Correct 181 ms 47656 KB Output is correct
7 Correct 182 ms 43384 KB Output is correct
8 Correct 186 ms 41592 KB Output is correct
9 Correct 175 ms 39708 KB Output is correct
10 Correct 142 ms 35960 KB Output is correct
11 Correct 160 ms 36112 KB Output is correct
12 Correct 153 ms 35960 KB Output is correct
13 Correct 154 ms 35960 KB Output is correct
14 Correct 139 ms 35192 KB Output is correct
15 Correct 135 ms 34296 KB Output is correct
16 Correct 84 ms 30968 KB Output is correct
17 Correct 90 ms 34584 KB Output is correct
18 Correct 113 ms 34672 KB Output is correct
19 Correct 92 ms 34668 KB Output is correct
20 Correct 96 ms 34592 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 35960 KB Output is correct
2 Correct 159 ms 36304 KB Output is correct
3 Incorrect 163 ms 35192 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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