oj.uz

Submission #316518

# Submission time Handle Problem Language Result Execution time Memory
316518 2020-10-26T13:50:42 Z Kevin_Zhang_TW Duathlon (APIO18_duathlon) C++17
23 / 100
 189 ms 55032 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], dep[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 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 189 ms 55032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21632 KB Output is correct
2 Correct 15 ms 21760 KB Output is correct
3 Correct 18 ms 21624 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 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 15 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 16 ms 21632 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 34680 KB Output is correct
2 Correct 142 ms 34764 KB Output is correct
3 Correct 137 ms 34680 KB Output is correct
4 Correct 143 ms 34808 KB Output is correct
5 Correct 140 ms 34680 KB Output is correct
6 Correct 169 ms 46328 KB Output is correct
7 Correct 168 ms 42232 KB Output is correct
8 Correct 165 ms 40236 KB Output is correct
9 Correct 160 ms 38472 KB Output is correct
10 Correct 141 ms 34680 KB Output is correct
11 Correct 142 ms 34808 KB Output is correct
12 Correct 151 ms 34680 KB Output is correct
13 Correct 138 ms 34680 KB Output is correct
14 Correct 131 ms 34040 KB Output is correct
15 Correct 115 ms 33400 KB Output is correct
16 Correct 75 ms 30336 KB Output is correct
17 Correct 83 ms 33260 KB Output is correct
18 Correct 82 ms 33264 KB Output is correct
19 Correct 87 ms 33388 KB Output is correct
20 Correct 86 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 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 141 ms 34680 KB Output is correct
2 Correct 164 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 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 -