Submission #676116

#TimeUsernameProblemLanguageResultExecution timeMemory
676116abysmalSprinkler (JOI22_sprinkler)C++14
100 / 100
1992 ms69844 KiB
#include<iostream> #include<stdio.h> #include<stdint.h> #include<vector> #include<algorithm> #include<utility> #include<set> #include<map> #include<queue> #include<stack> #include<string> using namespace std; const int64_t INF = (int64_t) 1e6 + 1; const int64_t mINF = 41; const int64_t MOD = (int64_t) 1e9 + 7; const int nbit = 11; const int ndig = 10; const int nchar = 26; const int p1 = 31; const int p2 = 53; const int D = 4; int dr[D] = {0, 1, 0, -1}; int dc[D] = {1, 0, -1, 0}; // 0 right // 1 down // 2 left // 3 up struct Node { int u; int w; Node(int u_, int w_) : u(u_), w(w_) {} bool operator < (const Node& o) const { return w > o.w; } }; struct Solution { int n; int64_t l; vector<int> p; vector<int> h; vector<vector<int> > mul; vector<vector<int> > adj; Solution() {} void solve() { cin >> n >> l; h.resize(n); adj.resize(n); p.resize(n, -1); mul.resize(n, vector<int>(mINF, 1)); for(int i = 0; i < n - 1; i++) { int u; int v; cin >> u >> v; u--; v--; adj[u].push_back(v); adj[v].push_back(u); } for(int i = 0; i < n; i++) { cin >> h[i]; } DFS(); int q; cin >> q; for(int i = 0; i < q; i++) { int t; cin >> t; if(t == 1) { int u; int d; int w; cin >> u >> d >> w; u--; while(u != -1 && d >= 0) { mul[u][d] = modmul(mul[u][d], w); // cerr << "u = " << u << " ; d = " << d << " ; w = " << w << "\n"; d--; u = p[u]; } // cerr << "\n"; } else { int u; cin >> u; u--; int ans = h[u]; int d = 0; // cerr << "2\n"; while(p[u] != -1 && d < mINF) { ans = modmul(ans, mul[u][d]); // cerr << "u = " << u << " ; d = " << d << " ; w = " << mul[u][d] << "\n"; if(d + 1 < mINF) { ans = modmul(ans, mul[u][d + 1]); // cerr << "w2 = " << mul[u][d + 1] << "\n"; } d++; u = p[u]; } while(d < mINF) { // cerr << "u = " << u << " ; d = " << d << " ; w = " << mul[u][d] << "\n"; ans = modmul(ans, mul[u][d]); d++; } // cerr << "\n"; cout << ans << "\n"; } } } void DFS(int u = 0) { for(int i = 0; i < (int) adj[u].size(); i++) { int v = adj[u][i]; if(v == p[u]) continue; p[v] = u; DFS(v); } } int modsub(int t1, int t2) { int res = t1 - t2; if(res < 0) res += MOD; return res; } int modadd(int t1, int t2) { int res = t1 + t2; if(res >= MOD) res -= MOD; return res; } int modmul(int t1, int t2) { int64_t res = 1LL * t1 * t2; return (res % l); } bool BIT(int& mask, int& j) { return (mask & MASK(j)); } int64_t MASK(int64_t j) { return (1LL << j); } }; void __startup() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); } int main() { __startup(); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { Solution().solve(); } return 0; }
#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...