Submission #1004607

#TimeUsernameProblemLanguageResultExecution timeMemory
1004607onbertSprinkler (JOI22_sprinkler)C++17
100 / 100
986 ms97212 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 2e5 + 5, m = 43; int n, M; vector<int> adj[maxn]; int d[maxn], fa[maxn]; bool vis[maxn]; void dfs(int u) { vis[u] = true; if (adj[u].size() == 0) return; for (int v:adj[u]) if (!vis[v]) { d[v] = d[u] + 1, fa[v] = u; dfs(v); } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> M; for (int i=1;i<=n-1;i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } fa[1] = -1, d[1] = 0; dfs(1); int val[n+1][m]; for (int i=1;i<=n;i++) for (int j=0;j<m;j++) val[i][j] = 1; for (int i=1;i<=n;i++) cin >> val[i][0]; int q; cin >> q; while (q--) { int t; cin >> t; if (t==1) { int x, D, w; cin >> x >> D >> w; int v = x; // cout << "test" << endl; for (int dep = d[x]+D; dep>=d[x]-D && dep >= 0; dep--) { // cout << v << endl; if (fa[v]!=-1 && dep-d[v] + d[x]-d[v] + 2 <= D) v = fa[v]; val[v][dep - d[v]] = val[v][dep - d[v]] * w % M; // cout << v << " " << dep - d[v] << endl; } } else if (t==2) { int x; cin >> x; int ans = 1; for (int v = x; v != -1 && d[x] - d[v] < m; v = fa[v]) { ans = ans * val[v][d[x] - d[v]] % M; // cout << v << " " << d[x] - d[v] << endl; } cout << ans << endl; } } }
#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...