oj.uz

Submission #316525

# Submission time Handle Problem Language Result Execution time Memory
316525 2020-10-26T14:06:24 Z Kevin_Zhang_TW Duathlon (APIO18_duathlon) C++17
31 / 100
 168 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] + 1;
		for (int u : be[x]) if (u != lst) {
			res -= sum * (sz[u]) * (nap - 2) * 2;
		}
	}
	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:92:2: note: in expansion of macro 'DE'
   92 |  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:104:3: note: in expansion of macro 'DE'
  104 |   DE(i + n);
      |   ^~
count_triplets.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
count_triplets.cpp:105:3: note: in expansion of macro 'debug'
  105 |   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 16 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 15 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 16 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 15 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 90 ms 34608 KB Output is correct
2 Correct 91 ms 34608 KB Output is correct
3 Correct 135 ms 39256 KB Output is correct
4 Correct 108 ms 35436 KB Output is correct
5 Correct 116 ms 34764 KB Output is correct
6 Correct 136 ms 38236 KB Output is correct
7 Correct 137 ms 36212 KB Output is correct
8 Correct 131 ms 36728 KB Output is correct
9 Correct 133 ms 34296 KB Output is correct
10 Correct 127 ms 34036 KB Output is correct
11 Correct 101 ms 31052 KB Output is correct
12 Correct 107 ms 30968 KB Output is correct
13 Correct 98 ms 30840 KB Output is correct
14 Correct 92 ms 30584 KB Output is correct
15 Correct 74 ms 29816 KB Output is correct
16 Correct 73 ms 29560 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 16 ms 21632 KB Output is correct
4 Correct 15 ms 21760 KB Output is correct
5 Correct 16 ms 21760 KB Output is correct
6 Correct 15 ms 21760 KB Output is correct
7 Correct 17 ms 21760 KB Output is correct
8 Correct 16 ms 21632 KB Output is correct
9 Correct 16 ms 21632 KB Output is correct
10 Correct 15 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 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 138 ms 34680 KB Output is correct
2 Correct 146 ms 34680 KB Output is correct
3 Correct 138 ms 34684 KB Output is correct
4 Correct 140 ms 34680 KB Output is correct
5 Correct 137 ms 34680 KB Output is correct
6 Correct 168 ms 46328 KB Output is correct
7 Correct 161 ms 42104 KB Output is correct
8 Correct 158 ms 40312 KB Output is correct
9 Correct 158 ms 38520 KB Output is correct
10 Correct 141 ms 34712 KB Output is correct
11 Correct 138 ms 34676 KB Output is correct
12 Correct 141 ms 34680 KB Output is correct
13 Correct 139 ms 34720 KB Output is correct
14 Correct 127 ms 34040 KB Output is correct
15 Correct 111 ms 33272 KB Output is correct
16 Correct 74 ms 30328 KB Output is correct
17 Correct 80 ms 33264 KB Output is correct
18 Correct 80 ms 33284 KB Output is correct
19 Correct 81 ms 33388 KB Output is correct
20 Correct 83 ms 33272 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21632 KB Output is correct
2 Correct 15 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 136 ms 34680 KB Output is correct
2 Correct 147 ms 34936 KB Output is correct
3 Incorrect 156 ms 33660 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 16 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 15 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 16 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 15 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 -