oj.uz

답안 #568223

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
568223 2022-05-25T01:35:21 Z maomao90 Sprinkler (JOI22_sprinkler) C++17
0 / 100
 4000 ms 294424 KB 
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 400005;
const int MAXD = 41;

int n, l;
vii adj[MAXN];
int h[MAXN];
int q;
int m;

ii p[MAXN];
int pre[MAXN], pst[MAXN], ptr = 1;
void dfs(int u) {
    REP (i, 0, adj[u].size()) {
        if (adj[u][i].FI == p[u].FI) {
            swap(adj[u][i], adj[u][SZ(adj[u]) - 1]);
            break;
        }
    }
    pre[u] = ptr;
    for (auto &[v, id] : adj[u]) {
        if (v == p[u].FI) continue;
        id = ptr++;
        p[v] = {u, id};
    }
    pst[u] = ptr;
    for (auto [v, id] : adj[u]) {
        if (v == p[u].FI) continue;
        dfs(v);
    }
}

void fwincre(int i, int x, int *fw) {
    for (; i <= MAXD; i += i & -i) fw[i] = (ll) fw[i] * x % l;
}
int fwqry(int i, int *fw) {
    int res = 1;
    for (; i > 0; i -= i & -i) res = (ll) res * fw[i] % l;
    return res;
}

int st[MAXN * 4][MAXD + 1];
void incre(int p, int l, int x) {
    int u = p + n;
    while (u) {
        fwincre(l, x, st[u]);
        u >>= 1;
    }
}
int qry(int s, int e, int l) {
    int a = s + n, b = e + n;
    int res = 1;
    while (a < b) {
        if (a & 1) {
            res = (ll) res * fwqry(l, st[a]) % ::l;
            a++;
        }
        if (b & 1) {
            b--;
            res = (ll) res * fwqry(l, st[b]) % ::l;
        }
        a >>= 1; b >>= 1;
    }
    return res;
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n >> l;
    REP (i, 1, n) {
        int a, b; cin >> a >> b;
        adj[a].pb({b, 0});
        adj[b].pb({a, 0});
    }
    int on = n;
    REP (i, 2, n + 1) {
        if (adj[i].size() == 1) {
            adj[i].pb({++on, 0});
            adj[on].pb({i, 0});
        }
    }
    dfs(1);
    m = 1;
    while (m < ptr) {
        m <<= 1;
    }
    REP (i, 0, MAXN * 4) {
        REP (j, 0, MAXD + 1) {
            st[i][j] = 1;
        }
    }
    REP (i, 1, n + 1) {
        cin >> h[i];
    }
    cin >> q;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, d, w; cin >> x >> d >> w;
            int u = x;
            REP (i, 2, d + 2) {
                if (p[u].FI == 0) break;
                int id = p[u].SE;
                u = p[u].FI;
                incre(id, i, w);
            }
            u = x;
            REP (i, 1, d + 2) {
                if (adj[u][0].FI == p[u].FI) break;
                int id = adj[u][0].SE;
                u = adj[u][0].FI;
                incre(id, i, w);
            }
        } else {
            int x; cin >> x;
            ll ans = h[x];
            ans = ans * qry(pre[x], pst[x], MAXD) % l;
            int u = x;
            RREP (i, MAXD - 1, 1) {
                if (p[u].FI == 0) break;
                int id = p[u].SE;
                u = p[u].FI;
                ans = ans * qry(pre[u], id, i) % l;
                ans = ans * qry(id + 1, pst[u], i) % l;
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

/*
3 1000000
1 2
2 3
1
1
1
2
1 2 1 2
2 3
*/

Compilation message

sprinkler.cpp: In function 'void dfs(int)':
sprinkler.cpp:13:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
   48 |     REP (i, 0, adj[u].size()) {
      |          ~~~~~~~~~~~~~~~~~~~            
sprinkler.cpp:48:5: note: in expansion of macro 'REP'
   48 |     REP (i, 0, adj[u].size()) {
      |     ^~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 272656 KB Output is correct
2 Incorrect 153 ms 272756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 175 ms 272708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 175 ms 272708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 153 ms 272628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 154 ms 272736 KB Output is correct
2 Correct 2553 ms 294424 KB Output is correct
3 Execution timed out 4074 ms 289784 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 272656 KB Output is correct
2 Incorrect 153 ms 272756 KB Output isn't correct
3 Halted 0 ms 0 KB -