提出 #72414091

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAX = 600001;
const int MAX_LOG = 30;
const int MOD = 998244353;

int P[MAX], A[MAX], B[MAX],
    parent[MAX][MAX_LOG], D[MAX], C[MAX],
    fac[MAX], inv[MAX], uf[MAX], sz[MAX];
vector<int> adj[MAX], val[MAX], arr[MAX], act[MAX];
bool chk[MAX];

int find(int X) { return X == uf[X] ? X : uf[X] = find(uf[X]); }
void uni(int X, int Y) {
    X = find(X), Y = find(Y);
    if (X == Y)
        return;
    else if (X > Y)
        swap(X, Y);
    uf[Y] = X, sz[X] += sz[Y], sz[Y] = 0;
}

int fpow(int N, int K) {
    int res = 1;
    while (K) {
        if (K & 1)
            res = res * N % MOD;
        N = N * N % MOD, K >>= 1;
    }
    return res;
}

int comb(int N, int K) {
    if (K < 0 || K > N)
        return 0;
    return fac[N] * inv[K] % MOD * inv[N - K] % MOD;
}

void dfs(int node, int par) {
    parent[node][0] = par, D[node] = D[par] + 1;
    for (int i = 1; i < MAX_LOG; i++)
        parent[node][i] = parent[parent[node][i - 1]][i - 1];

    for (int i : adj[node])
        dfs(i, node);
}

int lca(int X, int Y) {
    if (D[X] < D[Y])
        swap(X, Y);
    int diff = D[X] - D[Y];
    for (int i = 0; i < MAX_LOG; i++)
        if (diff & (1 << i))
            X = parent[X][i];

    for (int i = MAX_LOG - 1; i >= 0; i--)
        if (parent[X][i] != parent[Y][i])
            X = parent[X][i], Y = parent[Y][i];
    if (X != Y)
        X = parent[X][0];
    return X;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int N, M, ans = 1, X, Y, V, MD = 0;

    cin >> N >> M;
    for (int i = 0; i + 1 < N; i++)
        cin >> P[i];
    for (int i = 0; i < M; i++)
        cin >> A[i];
    for (int i = 0; i < M; i++)
        cin >> B[i];

    for (int i = 2; i <= N; i++)
        adj[P[i - 2]].push_back(i);

    dfs(1, 0);

    for (int i = 0; i + 1 < M; i++)
        C[i] = D[lca(B[i], B[i + 1])];

    fac[0] = 1, X = max(N, M);
    for (int i = 1; i <= X; i++)
        fac[i] = fac[i - 1] * i % MOD;
    inv[X] = fpow(fac[X], MOD - 2);
    for (int i = X - 1; i >= 0; i--)
        inv[i] = inv[i + 1] * (i + 1) % MOD;

    for (int i = 1; i <= N; i++)
        arr[D[i]].push_back(i), MD = max(D[i], MD);
    for (int i = 0; i < M; i++) {
        val[A[i]].push_back(i);
        uf[i] = i, sz[i] = 1;
    }
    for (int i = 0; i + 1 < M; i++)
        act[C[i]].push_back(i);

    // i, i + 1 swap -> max(A[i], A[i + 1]) <= C[i]

    for (int i = MD; i >= 1; i--) {
        for (int j : act[i])
            if (!chk[j] && !chk[j + 1])
                uni(j, j + 1);
        for (int j : arr[i]) {
            for (int k = 0; k < val[j].size(); k++) {
                X = k, Y = find(val[j][X]);
                while (k + 1 < val[j].size() && find(val[j][k + 1]) == Y)
                    k++;
                ans = ans * comb(sz[Y], k - X + 1) % MOD, sz[Y] -= k - X + 1;
                chk[Y] |= sz[Y] == 0;
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function 'int main()':
./Main.cpp:111:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             for (int k = 0; k < val[j].size(); k++) {
      |                             ~~^~~~~~~~~~~~~~~
./Main.cpp:113:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                 while (k + 1 < val[j].size() && find(val[j][k + 1]) == Y)
      |                        ~~~~~~^~~~~~~~~~~~~~~
./Main.cpp:70:30: warning: unused variable 'V' [-Wunused-variable]
   70 |     int N, M, ans = 1, X, Y, V, MD = 0;
      |                              ^

ジャッジ結果