제출 #588838

#제출 시각아이디문제언어결과실행 시간메모리
588838Red_InsideSprinkler (JOI22_sprinkler)C++17
38 / 100
766 ms76236 KiB
// #include <bits/stdc++.h> #define ll long long #define f first #define s second #define pb push_back #define mp make_pair #define o cout<<"BUG"<<endl; #define FOR(i, j, n) for(int j = i; j < n; ++j) #define forn(i, j, n) for(int j = i; j <= n; ++j) #define nfor(i, j, n) for(int j = n; j >= i; --j) #define sortv(vv) sort(vv.begin(), vv.end()) #define all(v) v.begin(), v.end() #define ld long double #define ull unsigned long long using namespace std; const int maxn=2e5+100,LOG=17, mod=1e9+7; int block = 320, timer = 0; const ld EPS = 1e-18; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define bt(i) (1 << (i)) //#define int ll const int inf=1e9+10; #define y1 yy #define prev pre #define pii pair <int, int> int n, q, anc[maxn], tin[maxn], tout[maxn], deep[maxn], sz[maxn]; ll L, h[maxn]; vector <int> edge[maxn]; vector <pii> vec[maxn]; vector <ll> t[maxn]; void dfs(int v, int pred = -1) { tin[v] = ++timer; vec[deep[v]].pb({tin[v], v}); for(auto to : edge[v]) { if(to == pred) continue; deep[to] = deep[v] + 1; anc[to] = v; dfs(to, v); } tout[v] = timer; } void push(int v, int tn) { t[tn][v * 2] = t[tn][v * 2] * t[tn][v] % L; t[tn][v * 2 + 1] = t[tn][v * 2 + 1] * t[tn][v] % L; t[tn][v] = 1; } void upd(int v, int tl, int tr, int l, int r, ll w, int tn) { if(l <= tl && tr <= r) { t[tn][v] = t[tn][v] * w % L; return; } if(l > tr || r < tl) return; push(v, tn); upd(v * 2, tl, (tl + tr) / 2, l, r, w, tn); upd(v * 2 + 1, (tl + tr) / 2 + 1, tr, l, r, w, tn); } ll get(int v, int tl, int tr, int pos, int tn) { if(tl == tr) return t[tn][v]; push(v, tn); if(pos <= (tl + tr) / 2) return get(v * 2, tl, (tl + tr) / 2, pos, tn); return get(v * 2 + 1, (tl + tr) / 2 + 1, tr, pos, tn); } void update(int x, ll w, int d) { if(sz[deep[x] + d] == 0) return; // cout << "UPDATE " << x << " " << w << " " << d << " " << tin[x] << " " << tout[x] << endl; // cout << "VECTOR\n"; // for(auto i : vec[deep[x] + d]) cout << " " << i.f << " " << i.s << endl; int L = lower_bound(all(vec[deep[x] + d]), mp(tin[x], 0)) - vec[deep[x] + d].begin() + 1; int R = upper_bound(all(vec[deep[x] + d]), mp(tout[x], inf)) - vec[deep[x] + d].begin(); upd(1, 1, sz[deep[x] + d], L, R, w, deep[x] + d); } main() { IOS cin >> n >> L; forn(1, i, n - 1) { int l, r; cin >> l >> r; edge[l].pb(r); edge[r].pb(l); } forn(1, i, n) cin >> h[i]; deep[1] = 1; dfs(1); forn(1, i, n) { sz[i] = vec[i].size(); t[i].assign(sz[i] * 4 + 10, 1); // build(1, 1, sz[i], i); } cin >> q; forn(1, i, q) { int ty; cin >> ty; if(ty == 1) { int x, d; ll w; cin >> x >> d >> w; if(d == 0) { h[x] = h[x] * w % L; continue; } if(d == 1) { h[x] = h[x] * w % L; if(anc[x] != 0) { h[anc[x]] = h[anc[x]] * w % L; } update(x, w, 1); } if(d == 2) { if(anc[x] != 0) { update(anc[x], w, 1); if(anc[anc[x]] != 0) { h[anc[anc[x]]] = h[anc[anc[x]]] * w % L; } h[anc[x]] = h[anc[x]] * w % L; } else { h[x] = h[x] * w % L; } update(x, w, 2); update(x, w, 1); } } else { int x; cin >> x; int pos = lower_bound(all(vec[deep[x]]), mp(tin[x], x)) - vec[deep[x]].begin() + 1; ll ans = h[x] * get(1, 1, sz[deep[x]], pos, deep[x]) % L; // cout << h[x] << " " << get(1, 1, sz[deep[x]], pos, deep[x]) << endl; cout << ans << "\n"; } } }

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

sprinkler.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main()
      | ^~~~
#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...