Submission #932878

#	Time	Username	Problem	Language	Result	Execution time	Memory
932878		alextodoran	Sprinkler (JOI22_sprinkler)	C++17	100 / 100	2854 ms	66668 KiB

sprinkler

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;


int _out_loc; char _out_buff[50000];

void write_ch(char ch)
{
    if (_out_loc == 50000) {
        fwrite(_out_buff, 1, 50000, stdout);
        _out_loc = 0;
        _out_buff[_out_loc++] = ch;
    } else {
        _out_buff[_out_loc++] = ch;
    }
}

void write_u32(unsigned int vu32)
{
    if (vu32 <= 9) {
        write_ch(vu32 + '0');
    } else {
        write_u32(vu32 / 10);
        write_ch(vu32 % 10 + '0');
    }
}

void write_appendix()
{
    fwrite(_out_buff, 1, _out_loc, stdout);
}

const int BUFFER_SIZE = 30000;

char buffer[BUFFER_SIZE];
int bpos = BUFFER_SIZE - 1;

char read_char ()
{
    bpos++;
    if(bpos == BUFFER_SIZE)
    {
        fread(buffer, sizeof(char), BUFFER_SIZE, stdin);
        bpos = 0;
    }
    return buffer[bpos];
}

bool isDigit[] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

int read_int ()
{
    int ans = 0;
    char c;
    while(isDigit[c = read_char()])
    {
        ans = ans * 10 + c - '0';
    }
    return ans;
}

const int N_MAX = 200000;
const int Q_MAX = 400000;

int N, MOD;
vector <int> adj[N_MAX + 2];
int H[N_MAX + 2];
int Q;
int type[Q_MAX + 2];
int vert[Q_MAX + 2];
int dist[Q_MAX + 2];
int water[Q_MAX + 2];

bool used[N_MAX + 2];

int parent[N_MAX + 2];
int depth[N_MAX + 2];

int order[N_MAX + 2];
int L[N_MAX + 2];
int R[N_MAX + 2];
int curr;

void dfs (int u) {
    order[++curr] = u;
    L[u] = R[u] = curr;
    for (int v : adj[u]) {
        if (v != parent[u]) {
            parent[v] = u;
            depth[v] = depth[u] + 1;
            dfs(v);
            R[u] = R[v];
        }
    }
}

vector <int> onDepth[N_MAX + 2];
int* SGT[N_MAX + 2];

void build (int* SGT, int node, int l, int r, vector <int> &arr) {
    if (l == r) {
        SGT[node] = 1;
        return;
    }
    SGT[node] = 1;
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    build(SGT, lSon, l, mid, arr);
    build(SGT, rSon, mid + 1, r, arr);
}
void build (int d) {
    build(SGT[d], 1, 0, (int) onDepth[d].size() - 1, onDepth[d]);
}

void init () {
    dfs(1);
    for (int i = 1; i <= N; i++) {
        int u = order[i];
        if (used[u] == true) {
            onDepth[depth[u]].push_back(u);
            onDepth[depth[u] + 1].push_back(u);
        }
    }
    for (int d = 0; d <= N; d++) {
        if (onDepth[d].empty() == false) {
            SGT[d] = new int[(int) onDepth[d].size() * 4 + 2];
            build(d);
        }
    }
}

void update (int* SGT, int node, int l, int r, int ul, int ur, int uval) {
    if (ul <= l && r <= ur) {
        SGT[node] = (ll) SGT[node] * uval % MOD;
        return;
    }
    int mid = (l + r) >> 1;
    int lSon = node << 1, rSon = lSon | 1;
    if (SGT[node] != 1) {
        SGT[lSon] = (ll) SGT[lSon] * SGT[node] % MOD;
        SGT[rSon] = (ll) SGT[rSon] * SGT[node] % MOD;
        SGT[node] = 1;
    }
    if (ul <= mid) {
        update(SGT, lSon, l, mid, ul, ur, uval);
    }
    if (mid + 1 <= ur) {
        update(SGT, rSon, mid + 1, r, ul, ur, uval);
    }
}
void update (int d, int ul, int ur, int uval) {
    if (ul <= ur) {
        update(SGT[d], 1, 0, (int) onDepth[d].size() - 1, ul, ur, uval);
    }
}

int query (int* SGT, int node, int l, int r, int qpos) {
    if (l == r) {
        return SGT[node];
    }
    int mid = (l + r) >> 1;
    int lSon = node << 1, rSon = lSon | 1;
    if (SGT[node] != 1) {
        SGT[lSon] = (ll) SGT[lSon] * SGT[node] % MOD;
        SGT[rSon] = (ll) SGT[rSon] * SGT[node] % MOD;
        SGT[node] = 1;
    }
    if (qpos <= mid) {
        return query(SGT, lSon, l, mid, qpos);
    } else {
        return query(SGT, rSon, mid + 1, r, qpos);
    }
}
int query (int d, int qpos) {
    return query(SGT[d], 1, 0, (int) onDepth[d].size() - 1, qpos);
}

int findL (int d, int node) {
    int l = 0, r = (int) onDepth[d].size();
    while (l < r) {
        int mid = (l + r) / 2;
        if (L[node] <= L[onDepth[d][mid]]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}
int findR (int d, int node) {
    int l = -1, r = (int) onDepth[d].size() - 1;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (R[onDepth[d][mid]] <= R[node]) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return r;
}

void upd (int d, int node, int w) {
    if (d > N || onDepth[d].empty() == true) {
        return;
    }
    update(d, findL(d, node), findR(d, node), w);
}

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

    N = read_int(); MOD = read_int();
//    N = N_MAX; MOD = 1000000000;
    for (int i = 1; i <= N - 1; i++) {
        int u, v;
        u = read_int(); v = read_int();
//        u = i + 1; v = rand() % i + 1;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int u = 1; u <= N; u++) {
        H[u] = read_int();
//        H[u] = rand() % MOD + 1;
    }
    Q = read_int();
//    Q = N_MAX;
    for (int i = 1; i <= Q; i++) {
        type[i] = read_int();
        vert[i] = read_int();
        if (type[i] == 1) {
            dist[i] = read_int();
            water[i] = read_int();
        } else {
            used[vert[i]] = true;
        }
    }

    init();

    for (int i = 1; i <= Q; i++) {
        int u = vert[i];
        if (type[i] == 1) {
            int r = dist[i];
            int w = water[i];
            int d = depth[u] + r;
            while (d > depth[u]) {
                upd(d, u, w);
                if (u != 1) {
                    u = parent[u];
                }
                d -= 2;
            }
            if (d == depth[u]) {
                H[u] = (ll) H[u] * w % MOD;
            }
        } else {
            write_u32((ll) H[u] * query(depth[u], findL(depth[u], u)) % MOD
                                * query(depth[u] + 1, findL(depth[u] + 1, u)) % MOD);
            write_ch('\n');
        }
    }
    write_appendix();

    return 0;
}

Compilation message (stderr)

sprinkler.cpp: In function 'int read_int()':
sprinkler.cpp:82:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   82 |     while(isDigit[c = read_char()])
      |                   ~~^~~~~~~~~~~~~
sprinkler.cpp: In function 'char read_char()':
sprinkler.cpp:54:14: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         fread(buffer, sizeof(char), BUFFER_SIZE, stdin);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17