oj.uz

Submission #316527

# Submission time Handle Problem Language Result Execution time Memory
316527 2020-10-26T14:10:02 Z Kevin_Zhang_TW Duathlon (APIO18_duathlon) C++17
31 / 100
 167 ms 46328 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;

	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;

		// need to minus ap thing
		// wanna know how many triples take ap as middle
		ll nap = child[x].size() - mid;
		ll sum = m - sz[x];
		for (int u : be[x]) if (u != lst) {
			res -= sum * (sz[u] - 1) * (nap - 2) * 2;
			sum += sz[u] - 1;
		}
	}
	DE(res);
	return res;
}
ll cal(int s) {
	int ob = bcc;

	dfscnt = 0;
	dfs1(s);
	ll m = dfscnt;


	for (int i = ob+1;i <= bcc;++i) {
		DE(i + n);
		debug(AI(child[i + n]));
	}
	return (m * (m-1) * (m-2)) - dfs2(s, m);
}
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:93:2: note: in expansion of macro 'DE'
   93 |  DE(res);
      |  ^~
count_triplets.cpp: In function 'll cal(int)':
count_triplets.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
count_triplets.cpp:105:3: note: in expansion of macro 'DE'
  105 |   DE(i + n);
      |   ^~
count_triplets.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
count_triplets.cpp:106:3: note: in expansion of macro 'debug'
  106 |   debug(AI(child[i + n]));
      |   ^~~~~

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 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 15 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 89 ms 34528 KB Output is correct
2 Correct 95 ms 34552 KB Output is correct
3 Correct 127 ms 39132 KB Output is correct
4 Correct 105 ms 35560 KB Output is correct
5 Correct 114 ms 34756 KB Output is correct
6 Correct 138 ms 38388 KB Output is correct
7 Correct 132 ms 36248 KB Output is correct
8 Correct 130 ms 36728 KB Output is correct
9 Correct 131 ms 34304 KB Output is correct
10 Correct 126 ms 34036 KB Output is correct
11 Correct 103 ms 31096 KB Output is correct
12 Correct 100 ms 30968 KB Output is correct
13 Correct 93 ms 30840 KB Output is correct
14 Correct 93 ms 30584 KB Output is correct
15 Correct 74 ms 29816 KB Output is correct
16 Correct 74 ms 29616 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 18 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 15 ms 21632 KB Output is correct
3 Correct 15 ms 21632 KB Output is correct
4 Correct 17 ms 21888 KB Output is correct
5 Correct 16 ms 21888 KB Output is correct
6 Correct 16 ms 21760 KB Output is correct
7 Correct 17 ms 21760 KB Output is correct
8 Correct 15 ms 21632 KB Output is correct
9 Correct 15 ms 21632 KB Output is correct
10 Correct 15 ms 21632 KB Output is correct
11 Correct 18 ms 21632 KB Output is correct
12 Correct 17 ms 21632 KB Output is correct
13 Correct 15 ms 21632 KB Output is correct
14 Correct 16 ms 21632 KB Output is correct
15 Correct 15 ms 21760 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 21668 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 34664 KB Output is correct
2 Correct 143 ms 34808 KB Output is correct
3 Correct 137 ms 34680 KB Output is correct
4 Correct 139 ms 34680 KB Output is correct
5 Correct 138 ms 34680 KB Output is correct
6 Correct 167 ms 46328 KB Output is correct
7 Correct 167 ms 42104 KB Output is correct
8 Correct 159 ms 40312 KB Output is correct
9 Correct 163 ms 38592 KB Output is correct
10 Correct 142 ms 34680 KB Output is correct
11 Correct 139 ms 34680 KB Output is correct
12 Correct 144 ms 34680 KB Output is correct
13 Correct 138 ms 34808 KB Output is correct
14 Correct 127 ms 34168 KB Output is correct
15 Correct 112 ms 33400 KB Output is correct
16 Correct 74 ms 30328 KB Output is correct
17 Correct 80 ms 33192 KB Output is correct
18 Correct 84 ms 33264 KB Output is correct
19 Correct 86 ms 33388 KB Output is correct
20 Correct 85 ms 33272 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 15 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 140 ms 34680 KB Output is correct
2 Correct 146 ms 35064 KB Output is correct
3 Incorrect 146 ms 33784 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 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 15 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 -