이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef vector < int > vi;
typedef long long ll;
const int N = 2e5 + 500;
const int LOG = 20;
const int INF = 0x3f3f3f3f;
int MOD;
inline int mul(int A, int B){
return (ll)A * B % MOD;
}
struct tournament{
int siz, off;
vi T;
void init(int _siz){
siz = _siz; off = 1;
while(off < siz) off <<= 1;
T.resize(2 * off);
for(int &x : T) x = 1;
}
int get(int x){
int ret = 1;
for(x = (x + off); x ; x /= 2)
ret = mul(ret, T[x]);
return ret;
}
void Tmultiply(int i, int a, int b, int lo, int hi, int x){
if(lo <= a && b <= hi) { T[i] = mul(T[i], x); return; }
if(a > hi || b < lo) return;
Tmultiply(2 * i, a, (a + b) / 2, lo, hi, x);
Tmultiply(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, x);
}
inline void multiply(int l, int r, int x){
if(r < l ) return;
Tmultiply(1, 0, off - 1, l, r, x);
}
};
tournament T[N][41];
int cen[N], siz[N], par[N], dep[N][LOG], gore[N], tko[N][41];
vector < int > pos;
int L[N][41], R[N][41], gdje[N][LOG], osb[N], gdje2[N][LOG];
int n, q;
vector < int > v[N];
void dfs(int x, int lst){
siz[x] = 1; pos.PB(x);
for(int y : v[x]){
if(cen[y] != INF || y == lst) continue;
dfs(y, x); siz[x] += siz[y];
}
}
int TATA, RAZ;
void dfs2(int x, int lst, int dis){
gdje2[x][RAZ] = dis;
if(dis <= 40) {
gdje[x][RAZ] = tko[TATA][dis];
tko[TATA][dis]++;
}
for(int y : v[x]){
if(y == lst || cen[y] <= RAZ) continue;
dfs2(y, x, dis + 1);
}
}
int nadi_centroid(int x){
pos.clear(); dfs(x, x);
int bst = x;
for(int y : pos)
if(2 * siz[y] >= (int)pos.size() && siz[y] < siz[bst])
bst = y;
return bst;
}
int centroidna(int x, int dub){
x = nadi_centroid(x);
cen[x] = dub;
for(int y : v[x]){
if(cen[y] != INF) continue;
int nov = centroidna(y, dub + 1);
for(int i = 1;i <= 40;i++)
L[nov][i] = tko[x][i];
TATA = x; RAZ = dub;
dfs2(y, x, 1);
for(int i = 1;i <= 40;i++)
R[nov][i] = tko[x][i] - 1;
par[nov] = x;
}
return x;
}
void obradi(int x, int d, int k){
osb[x] = mul(osb[x], k);
for(int i = 1;i <= d;i++)
T[x][i].multiply(0, T[x][i].siz - 1, k);
int lst = x, poc = x;
x = par[x];
while(x){
if(gdje2[poc][cen[x]] <= d)
osb[x] = mul(osb[x], k);
for(int i = 1;i <= d - gdje2[poc][cen[x]];i++){
T[x][i].multiply(0, L[lst][i] - 1, k);
T[x][i].multiply(R[lst][i] + 1, T[x][i].siz - 1, k);
}
lst = x; x = par[x];
}
}
int get(int x){
int ret = osb[x];
int cur = x;
while(cur){
if(gdje[x][cen[cur]] != -1){
ret = mul(ret, T[cur][gdje2[x][cen[cur]]].get(gdje[x][cen[cur]]));
}
cur = par[cur];
}
return ret;
}
int main(){
memset(cen, INF, sizeof(cen));
memset(gdje, -1, sizeof(gdje));
scanf("%d%d", &n, &MOD);
for(int i = 1;i < n;i++){
int x, y; scanf("%d%d", &x, &y);
v[x].PB(y), v[y].PB(x);
}
for(int i = 1;i <= n;i++)
scanf("%d", osb + i);
centroidna(1, 1);
for(int i = 1;i <= n;i++)
for(int j = 0;j <= 40;j++)
T[i][j].init(tko[i][j]);
scanf("%d", &q);
for(;q--;){
int ty; scanf("%d", &ty);
if(ty == 2){
int x; scanf("%d", &x);
printf("%d\n", get(x));
}
else{
int x, d, k; scanf("%d%d%d", &x, &d, &k);
obradi(x, d, k);
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
141 | scanf("%d%d", &n, &MOD);
| ~~~~~^~~~~~~~~~~~~~~~~~
sprinkler.cpp:143:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
143 | int x, y; scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:147:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
147 | scanf("%d", osb + i);
| ~~~~~^~~~~~~~~~~~~~~
sprinkler.cpp:152:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
sprinkler.cpp:154:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
154 | int ty; scanf("%d", &ty);
| ~~~~~^~~~~~~~~~~
sprinkler.cpp:156:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
156 | int x; scanf("%d", &x);
| ~~~~~^~~~~~~~~~
sprinkler.cpp:160:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
160 | int x, d, k; scanf("%d%d%d", &x, &d, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | 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... |