QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#770276	#4885. Triangular Cactus Paths	I_be_wanna	Compile Error	/	/	C++20	6.5kb	2024-11-21 21:20:33	2024-11-21 21:20:34

Judging History

你现在查看的是最新测评结果

[2024-11-21 21:20:34]
评测

测评结果：Compile Error
用时：0ms
内存：0kb

查看

[2024-11-21 21:20:33]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int     long long
#define pb      push_back
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fs      first
#define sc      second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
#define fl '\n'

int n, m;
vi g[200005];
vi t[200005];

bool mk[200005];
int low[200005], num[200005];
int cc = 1;
int prnt[200005];
bool lt[200005];
bool ld[200005];
int dd[200005];

void dfs(int u, int p) {
	mk[u] = true;
	num[u] = cc;
	low[u] = cc;
	cc++;
	for (auto v : g[u]) {
		if (v == p)
			continue;
		if (!mk[v]) {
			prnt[v] = u;
			dfs(v, u);
			t[u].pb(v);
			low[u] = min(low[u], low[v]);
		}else
			low[u] = min(low[u], num[v]);
	}
	if (low[u] == num[p]) {
		lt[u] = 1;
	}
	if (low[u] == num[prnt[p]]) {
		ld[u] = 1;
	}
}

int pr[200005][25];
int lvl[200005];
int dp[200005];

int f[200005];

void build(int u) {
	if (lt[u])
		dp[u]++;
	
	//cout<<u<<" "<<ld[u]<<fl;
	if (ld[u])
		dd[u]++;
	for (int i = 1; i <= __lg(lvl[u]); i++) {
		pr[u][i] = pr[pr[u][i - 1]][i - 1];
	}
	for (auto v : t[u]) {
		pr[v][0] = u;
		lvl[v] = lvl[u] + 1;
		dp[v] = dp[u];
		dd[v] = dd[u];
		build(v);
	}
}

int kthp(int u, int k) {
	int l = __lg(k);
	while (k) {
		u = pr[u][l];
		k -= (1ll << l);
		l = __lg(k);
	}
	return u;
}

int lca(int a, int b) {
	if (lvl[a] < lvl[b])
		swap(a, b);
	a = kthp(a, lvl[a] - lvl[b]);
	if (a == b)
		return a;
	for (int i = __lg(lvl[a]); i >= 0; i--) {
		if (pr[a][i] != pr[b][i]) {
			a = pr[a][i];
			b = pr[b][i];
		}
	}
	return pr[a][0];
}

int mod = 998244353;
int qpow(int a, int b) {
	if (b == 0)
		return 1;
	if (b == 1)
		return a;
	int r = qpow(a, b / 2);
	int ret = r * r % mod;
	if (b % 2 == 0) {
		return ret;
	} else {
		return ret * a % mod;
	}
}

int inv(int a, int b) { return a * qpow(b, mod - 2) % mod; }

int C(int n, int k) {
	if (k > n)
		return 0;
	return inv(f[n], f[k] * f[n - k] % mod);
}

void solve() {
	cin >> n >> m;

	f[0] = 1;
	for (int i = 1; i <= n; i++) {
		f[i] = (f[i - 1] * i) % mod;
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		 cin >> a >> b;
		// /*
		// if (i < 1e5) {
		// 	a = i + 1;
		// 	b = i + 1 + 1;
		// } else {
		// 	a = 2 * (i - 1e5) + 1;
		// 	b = 2 * (i - 1e5) + 2 + 1;
		// }
		// */
		g[a].pb(b);
		g[b].pb(a);
	}

	dfs(1, -1);
	lvl[1] = 0;
	build(1);
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int a, b, k;
		cin >> a >> b >> k;
		if (a == b) {
			if (k == 0)
				cout << 1 << fl;
			else
				cout << 0 << fl;
			continue;
		}

		int lc = lca(a, b);

		int rs = lvl[a] - lvl[lc] + lvl[b] - lvl[lc];
		rs -= dd[a] - dd[lc];
		rs -= dd[b] - dd[lc];
		//if ((a == lc || b == lc) && a != b && lt[lc])
		//	rs--;

		//if (lt[a])
		//	rs++;
		//if (lt[b])
		//	rs++;
 
		int ck = dp[a] - dp[lc] + dp[b] - dp[lc];
		if(a != lc && ld[kthp(a, lvl[a] - lvl[lc] - 1)])rs++,ck++;
		if(b != lc && ld[kthp(b, lvl[b] - lvl[lc] - 1)])rs++,ck++;

		// if ((a != lc && low[kthp(a, lvl[a] - lvl[lc] - 1)] == num[prnt[lc]] &&
		//      lc != 1) ||
		//     (b != lc && low[kthp(b, lvl[b] - lvl[lc] - 1)] == num[prnt[lc]] &&
		//      lc != 1)) {
		// 	ck++;
		// }
		//cout<<a<<" "<<b<<" :"<<rs<<" "<<ck<<fl;
		if (rs <= k) {
			cout << C(ck, k - rs) << fl;
		} else {
			cout << 0 << fl;
		}
		// cout << C(50000, k - 50000) << "\n";
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}
/*#include <bits/stdc++.h>
using namespace std;
#define int     long long
#define pb      push_back
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fs      first
#define sc      second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
#define fl '\n'

int n, m;
vi g[200005];
vi t[200005];

bool mk[200005];
int low[200005], num[200005];
int cc = 1;
int prnt[200005];
bool lt[200005];
bool ld[200005];
int dd[200005];

void dfs(int u, int p) {
	mk[u] = true;
	num[u] = cc;
	low[u] = cc;
	cc++;
	for (auto v : g[u]) {
		if (v == p)
			continue;
		if (!mk[v]) {
			prnt[v] = u;
			dfs(v, u);
			t[u].pb(v);
			low[u] = min(low[u], low[v]);
		}else
			low[u] = min(low[u], num[v]);
	}
	if (low[u] == num[p]) {
		lt[u] = 1;
	}
	if (low[u] == num[prnt[p]]) {
		ld[u] = 1;
	}
}

int pr[200005][25];
int lvl[200005];
int dp[200005];

int f[200005];

void build(int u) {
	if (lt[u])
		dp[u]++;
	
	//cout<<u<<" "<<ld[u]<<fl;
	if (ld[u])
		dd[u]++;
	for (int i = 1; i <= __lg(lvl[u]); i++) {
		pr[u][i] = pr[pr[u][i - 1]][i - 1];
	}
	for (auto v : t[u]) {
		pr[v][0] = u;
		lvl[v] = lvl[u] + 1;
		dp[v] = dp[u];
		dd[v] = dd[u];
		build(v);
	}
}

int kthp(int u, int k) {
	int l = __lg(k);
	while (k) {
		u = pr[u][l];
		k -= (1ll << l);
		l = __lg(k);
	}
	return u;
}

int lca(int a, int b) {
	if (lvl[a] < lvl[b])
		swap(a, b);
	a = kthp(a, lvl[a] - lvl[b]);
	if (a == b)
		return a;
	for (int i = __lg(lvl[a]); i >= 0; i--) {
		if (pr[a][i] != pr[b][i]) {
			a = pr[a][i];
			b = pr[b][i];
		}
	}
	return pr[a][0];
}

int mod = 998244353;
int qpow(int a, int b) {
	if (b == 0)
		return 1;
	if (b == 1)
		return a;
	int r = qpow(a, b / 2);
	int ret = r * r % mod;
	if (b % 2 == 0) {
		return ret;
	} else {
		return ret * a % mod;
	}
}

int inv(int a, int b) { return a * qpow(b, mod - 2) % mod; }

int C(int n, int k) {
	if (k > n)
		return 0;
	return inv(f[n], f[k] * f[n - k] % mod);
}

void solve() {
	cin >> n >> m;

	f[0] = 1;
	for (int i = 1; i <= n; i++) {
		f[i] = (f[i - 1] * i) % mod;
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		 cin >> a >> b;
		// /*
		// if (i < 1e5) {
		// 	a = i + 1;
		// 	b = i + 1 + 1;
		// } else {
		// 	a = 2 * (i - 1e5) + 1;
		// 	b = 2 * (i - 1e5) + 2 + 1;
		// }
		// */
		g[a].pb(b);
		g[b].pb(a);
	}

	dfs(1, -1);
	lvl[1] = 0;
	build(1);
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int a, b, k;
		cin >> a >> b >> k;
		if (a == b) {
			if (k == 0)
				cout << 1 << fl;
			else
				cout << 0 << fl;
			continue;
		}

		int lc = lca(a, b);

		int rs = lvl[a] - lvl[lc] + lvl[b] - lvl[lc];
		rs -= dd[a] - dd[lc];
		rs -= dd[b] - dd[lc];
		//if ((a == lc || b == lc) && a != b && lt[lc])
		//	rs--;

		//if (lt[a])
		//	rs++;
		//if (lt[b])
		//	rs++;
	cin.tie(0);
	solve();
	return 0;
}*/

源文件, 语言: C++20

详细

answer.code:346:17: error: ‘g’ does not name a type
  346 |                 g[a].pb(b);
      |                 ^
answer.code:347:17: error: ‘g’ does not name a type
  347 |                 g[b].pb(a);
      |                 ^
answer.code:348:9: error: expected declaration before ‘}’ token
  348 |         }
      |         ^
answer.code:350:12: error: expected constructor, destructor, or type conversion before ‘(’ token
  350 |         dfs(1, -1);
      |            ^
answer.code:351:9: error: ‘lvl’ does not name a type; did you mean ‘ll’?
  351 |         lvl[1] = 0;
      |         ^~~
      |         ll
answer.code:352:14: error: expected constructor, destructor, or type conversion before ‘(’ token
  352 |         build(1);
      |              ^
answer.code:354:9: error: ‘cin’ does not name a type
  354 |         cin >> q;
      |         ^~~
answer.code:355:9: error: expected unqualified-id before ‘for’
  355 |         for (int i = 0; i < q; i++) {
      |         ^~~
answer.code:355:25: error: ‘i’ does not name a type; did you mean ‘vi’?
  355 |         for (int i = 0; i < q; i++) {
      |                         ^
      |                         vi
answer.code:355:32: error: ‘i’ does not name a type; did you mean ‘vi’?
  355 |         for (int i = 0; i < q; i++) {
      |                                ^
      |                                vi
answer.code:381:3: error: expected unqualified-id before ‘/’ token
  381 | }*/
      |   ^