이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
____ ____ ____ ____ ____
||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;
}
컴파일 시 표준 에러 (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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |