oj.uz

Submission #316526

# Submission time Handle Problem Language Result Execution time Memory
316526 2020-10-26T14:08:41 Z Kevin_Zhang_TW Duathlon (APIO18_duathlon) C++17
31 / 100
 173 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;
			sum += sz[u];
		}
	}
	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 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 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 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 88 ms 34608 KB Output is correct
3 Correct 129 ms 39132 KB Output is correct
4 Correct 107 ms 35432 KB Output is correct
5 Correct 111 ms 34768 KB Output is correct
6 Correct 129 ms 38388 KB Output is correct
7 Correct 134 ms 36136 KB Output is correct
8 Correct 134 ms 36728 KB Output is correct
9 Correct 134 ms 34296 KB Output is correct
10 Correct 135 ms 34036 KB Output is correct
11 Correct 103 ms 31096 KB Output is correct
12 Correct 112 ms 30968 KB Output is correct
13 Correct 96 ms 30824 KB Output is correct
14 Correct 98 ms 30712 KB Output is correct
15 Correct 81 ms 29816 KB Output is correct
16 Correct 73 ms 29608 KB Output is correct
17 Correct 18 ms 23552 KB Output is correct
18 Correct 19 ms 23600 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 15 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 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 21632 KB Output is correct
9 Correct 16 ms 21632 KB Output is correct
10 Correct 16 ms 21760 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 143 ms 34680 KB Output is correct
3 Correct 138 ms 34680 KB Output is correct
4 Correct 139 ms 34700 KB Output is correct
5 Correct 138 ms 34680 KB Output is correct
6 Correct 170 ms 46328 KB Output is correct
7 Correct 173 ms 42232 KB Output is correct
8 Correct 160 ms 40252 KB Output is correct
9 Correct 151 ms 38440 KB Output is correct
10 Correct 135 ms 34680 KB Output is correct
11 Correct 138 ms 34728 KB Output is correct
12 Correct 136 ms 34680 KB Output is correct
13 Correct 138 ms 34680 KB Output is correct
14 Correct 125 ms 34168 KB Output is correct
15 Correct 112 ms 33272 KB Output is correct
16 Correct 74 ms 30328 KB Output is correct
17 Correct 82 ms 33260 KB Output is correct
18 Correct 81 ms 33264 KB Output is correct
19 Correct 83 ms 33388 KB Output is correct
20 Correct 84 ms 33292 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 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 138 ms 34808 KB Output is correct
2 Correct 140 ms 34936 KB Output is correct
3 Incorrect 145 ms 33656 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 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 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 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 -