제출 #1353100

#제출 시각아이디문제언어결과실행 시간메모리
1353100retardeSprinkler (JOI22_sprinkler)C++20
41 / 100
4098 ms170196 KiB
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(), (x).end()

typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;

// const int mod = 1e9 + 7;
const int inf = INTMAX_MAX;
const bool tc = false;

int n, mod;
const int mxn = 2e5 + 5;
int h[mxn], par[mxn], ti[mxn], lf[mxn][41], rg[mxn][41]; vi adj[mxn];

void dfs(int node, int prev) {
    for (int i = 1; i <= 40; i++) {
        lf[node][i] = 1e18;
        rg[node][i] = -1e18;
    }
    lf[node][0] = rg[node][0] = ti[node];

    for (auto &neighbour : adj[node]) {
        if (neighbour == prev) continue;
        dfs(neighbour, node);
    }

    for (int i = 1; i <= 40; i++) {
        for (auto &neighbour : adj[node]) {
            if (neighbour == prev) continue;
            lf[node][i] = min(lf[node][i], lf[neighbour][i - 1]);
            rg[node][i] = max(rg[node][i], rg[neighbour][i - 1]);
        }
    }
}

int seg[4 * mxn];

void build(int i, int l, int r) {
    if (l > r) return;
    seg[i] = 1;
    if (l == r) {seg[i] = h[l]; return;}
    int mid = (l+r) / 2;
    build(i*2, l, mid);
    build(i*2+1, mid+1, r);
}

void update(int i, int l, int r, int ql, int qr, int qx) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        seg[i] *= qx;
        seg[i] %= mod;
        return;
    }
    int mid = (l+r)/2;
    update(i*2, l, mid, ql, qr, qx);
    update(i*2+1, mid+1, r, ql, qr, qx);
}

int query(int i, int l, int r, int ql, int qr, int cur=1) {
    if (l > r) return 1;
    if (qr < l || r < ql) return 1;
    cur *= seg[i];
    cur %= mod;
    if (ql <= l && r <= qr) return cur;
    int mid = (l+r)/2;
    return (query(i*2, l, mid, ql, qr,cur) * query(i*2+1, mid+1, r, ql, qr,cur))%mod;
}

void mul(int l, int r, int x) { update(1, 0, n - 1, l, r, x); }
int qry(int x) { return query(1, 0, n - 1, x, x, 1); }

inline void solve() {
    cin >> n >> mod;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v; u--; v--;
        adj[u].pb(v); adj[v].pb(u);
    }

    queue<pii> bfs; int t = 0;
    bfs.push({0, -1});
    while (bfs.size()) {
        auto cur = bfs.front();
        int node = cur.fi; int p = cur.se;
        par[node] = p;
        ti[node] = t++; 
        bfs.pop();

        for (auto &neighbour : adj[node]) {
            if (neighbour == p) continue;
            bfs.push({neighbour, node});
        }
    }

    dfs(0, -1);

    // use time
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        h[ti[i]] = x;
    }

    build(1, 0, n - 1);

    int q; cin >> q;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, d, w;
            cin >> x >> d >> w;
            x--; int h = d;

            if (d == 0) {
                mul(ti[x], ti[x], w);
                continue;
            }

            for (int i = 0; i <= d-1; i++) {
                if (x == 0) break;
                // h below and h -1
                pii x1 = {lf[x][h], rg[x][h]}, x2 = {lf[x][h - 1], rg[x][h - 1]};
                if (x1.fi != -1) {
                    mul(x1.fi, x1.se, w);
                }
                if (x2.fi != -1) {
                    mul(x2.fi, x2.se, w);
                }
                h--;
                x = par[x];
            }

            // do everythign
            for (int k = 0; k <= h; k++) {
                pii p = {lf[x][k], rg[x][k]};
                if (p.fi != -1) mul(p.fi, p.se, w);
            }

            // cout << "done\n";
        } else {
            int x; cin >> x; x--;
            cout << qry(ti[x]) << '\n';
            // cout << h[ti[x]] << '\n';
        }
    }
}

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

signed main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    //setIO();

    int t = 1;
    if (tc) {
        cin >> t;
    }

    while (t--) {
        solve();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

sprinkler.cpp: In function 'void setIO(std::string)':
sprinkler.cpp:169:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:170:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...