oj.uz

Submission #316517

# Submission time Handle Problem Language Result Execution time Memory
316517 2020-10-26T13:49:03 Z Kevin_Zhang_TW Duathlon (APIO18_duathlon) C++17
31 / 100
 175 ms 48248 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;
#define int ll
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(ll, ll)':
count_triplets.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
count_triplets.cpp:29:3: note: in expansion of macro 'DE'
   29 |   DE(x, u);
      |   ^~
count_triplets.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
count_triplets.cpp:43:7: note: in expansion of macro 'DE'
   43 |       DE(tp, gid);
      |       ^~
count_triplets.cpp: In function 'll dfs2(ll, ll, ll)':
count_triplets.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
count_triplets.cpp:58:1: note: in expansion of macro 'DE'
   58 | DE(x, sz[x]);
      | ^~
count_triplets.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
count_triplets.cpp:85:2: note: in expansion of macro 'DE'
   85 |  DE(res);
      |  ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21504 KB Output is correct
2 Correct 14 ms 21504 KB Output is correct
3 Correct 15 ms 21504 KB Output is correct
4 Correct 15 ms 21504 KB Output is correct
5 Correct 16 ms 21504 KB Output is correct
6 Correct 15 ms 21504 KB Output is correct
7 Incorrect 15 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 14 ms 21504 KB Output is correct
3 Correct 15 ms 21504 KB Output is correct
4 Correct 15 ms 21504 KB Output is correct
5 Correct 16 ms 21504 KB Output is correct
6 Correct 15 ms 21504 KB Output is correct
7 Incorrect 15 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 97 ms 38300 KB Output is correct
2 Correct 96 ms 38172 KB Output is correct
3 Correct 130 ms 41116 KB Output is correct
4 Correct 114 ms 39280 KB Output is correct
5 Correct 117 ms 36848 KB Output is correct
6 Correct 137 ms 40304 KB Output is correct
7 Correct 146 ms 38260 KB Output is correct
8 Correct 148 ms 38904 KB Output is correct
9 Correct 137 ms 36212 KB Output is correct
10 Correct 127 ms 35960 KB Output is correct
11 Correct 111 ms 33144 KB Output is correct
12 Correct 106 ms 33024 KB Output is correct
13 Correct 102 ms 32888 KB Output is correct
14 Correct 97 ms 32632 KB Output is correct
15 Correct 76 ms 31864 KB Output is correct
16 Correct 76 ms 31608 KB Output is correct
17 Correct 20 ms 25600 KB Output is correct
18 Correct 19 ms 25472 KB Output is correct
19 Correct 20 ms 25344 KB Output is correct
20 Correct 19 ms 25344 KB Output is correct
21 Correct 19 ms 25344 KB Output is correct
22 Correct 19 ms 25216 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 37652 KB Output is correct
2 Correct 149 ms 37752 KB Output is correct
3 Correct 148 ms 37764 KB Output is correct
4 Correct 147 ms 37880 KB Output is correct
5 Correct 144 ms 37624 KB Output is correct
6 Correct 175 ms 48248 KB Output is correct
7 Correct 175 ms 44920 KB Output is correct
8 Correct 170 ms 43000 KB Output is correct
9 Correct 164 ms 41208 KB Output is correct
10 Correct 150 ms 37752 KB Output is correct
11 Correct 145 ms 37732 KB Output is correct
12 Correct 147 ms 37624 KB Output is correct
13 Correct 147 ms 37624 KB Output is correct
14 Correct 139 ms 36776 KB Output is correct
15 Correct 122 ms 35704 KB Output is correct
16 Correct 78 ms 32376 KB Output is correct
17 Correct 89 ms 35560 KB Output is correct
18 Correct 88 ms 35560 KB Output is correct
19 Correct 94 ms 35928 KB Output is correct
20 Correct 92 ms 35688 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 151 ms 37752 KB Output is correct
2 Correct 155 ms 37752 KB Output is correct
3 Incorrect 162 ms 36856 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 14 ms 21504 KB Output is correct
3 Correct 15 ms 21504 KB Output is correct
4 Correct 15 ms 21504 KB Output is correct
5 Correct 16 ms 21504 KB Output is correct
6 Correct 15 ms 21504 KB Output is correct
7 Incorrect 15 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 14 ms 21504 KB Output is correct
3 Correct 15 ms 21504 KB Output is correct
4 Correct 15 ms 21504 KB Output is correct
5 Correct 16 ms 21504 KB Output is correct
6 Correct 15 ms 21504 KB Output is correct
7 Incorrect 15 ms 21504 KB Output isn't correct
8 Halted 0 ms 0 KB -