WA+MLE，样例过不了，拍不出来哪里错了

CEFqwq @ 2024-03-24 19:40:24

#include<bits/stdc++.h>
#define mxn 100005
using namespace std;
vector<int> G[mxn], IG[mxn];
int a[mxn], sm[mxn], id[mxn], ml[mxn], in[mxn], out[mxn];
int rep[mxn];
int n, m, q;
queue<int> tq;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int j = 1; j <= n; j++){
        int op;
        cin >> op;
        if (op == 1){
            cin >> id[j] >> sm[j];
            ml[j] = 1;
        }else if (op == 2)
            cin >> ml[j];
        else{
            ml[j] = 1;
            int ni;
            cin >> ni;
            for (int i = 1; i <= ni; i++){
                int u;
                cin >> u;
                G[j].push_back(u);
                IG[u].push_back(j);
                in[u]++;
                out[j]++;
            }
        }
    }
    ml[0] = 1;
    rep[0] = 1;
    cin >> q;
    for (int i = 1; i <= q; i++){
        int u;
        cin >> u;
        G[0].push_back(u);
        IG[u].push_back(0);
        out[0]++;
        in[u]++;
    }
    for (int i = 1; i <= n; i++)
        if (!out[i])
            tq.push(i);
    while (!tq.empty()){
        int u = tq.front();
        tq.pop();
        for (auto v : IG[u]){
            out[v]--;
            ml[v] *= ml[u];
            if (!out[v])
                tq.push(v);
        }
    }
    for (int i = 1; i <= n; i++)
        if (!in[i])
            tq.push(i);
    while (!tq.empty()){
        int u = tq.front(), nml = 1;
        tq.pop();
        for (auto v : G[u]){
            in[v]--;
            rep[v] = (rep[v] + rep[u] * nml) % 998244353;
            nml = (nml * rep[v]) % 998244353;
            if (!in[v])
                tq.push(v);
        }
    }
    for (int i = 1; i <= n; i++)
        a[i] = (1ll * a[i] * ml[0]) % 998244353;
    for (int i = 1; i <= m; i++)
        a[id[i]] = (a[id[i]] + rep[i] * sm[i]) % 998244353;
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
}

by CEFqwq @ 2024-03-24 20:02:37

调出来一个 sb 错误。

by CEFqwq @ 2024-03-24 20:16:25

变成了 WA10pts

#include<bits/stdc++.h>
#define int long long
#define mxn 100005
using namespace std;
vector<int> G[mxn], IG[mxn];
int a[mxn], sm[mxn], id[mxn], ml[mxn], in[mxn], out[mxn];
int rep[mxn];
int n, m, q;
queue<int> tq;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for (int j = 1; j <= m; j++){
        int op;
        cin >> op;
        if (op == 1){
            cin >> id[j] >> sm[j];
            ml[j] = 1;
        }else if (op == 2)
            cin >> ml[j];
        else{
            ml[j] = 1;
            int ni;
            cin >> ni;
            for (int i = 1; i <= ni; i++){
                int u;
                cin >> u;
                G[j].push_back(u);
                IG[u].push_back(j);
                in[u]++;
                out[j]++;
            }
        }
    }
    ml[0] = 1;
    rep[0] = 1;
    cin >> q;
    for (int i = 1; i <= q; i++){
        int u;
        cin >> u;
        G[0].push_back(u);
        IG[u].push_back(0);
        out[0]++;
        in[u]++;
    }
    for (int i = 0; i <= m; i++)
        if (!out[i])
            tq.push(i);
    while (!tq.empty()){
        int u = tq.front();
        tq.pop();
        for (auto v : IG[u]){
            out[v]--;
            ml[v] *= ml[u];
            if (!out[v])
                tq.push(v);
        }
    }
    for (int i = 0; i <= m; i++)
        if (!in[i])
            tq.push(i);
    while (!tq.empty()){
        int u = tq.front(), nml = 1;
        tq.pop();
        for (auto v : G[u]){
            in[v]--;
            rep[v] = (rep[v] + rep[u] * nml) % 998244353;
            nml = (nml * ml[v]) % 998244353;
            if (!in[v])
                tq.push(v);
        }
    }
    for (int i = 1; i <= n; i++)
        a[i] = (1ll * a[i] * ml[0]) % 998244353;
    for (int i = 1; i <= m; i++){
    //  cout << id[i] << " " << rep[i] << " " << sm[i] << "\n";
        a[id[i]] = (a[id[i]] + rep[i] * sm[i]) % 998244353;
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
}

by CEFqwq @ 2024-03-24 20:26:00

一个乘法没开 long long，20 了。