oj.uz

Submission #999556

# Submission time Handle Problem Language Result Execution time Memory
999556 2024-06-15T19:29:11 Z Saul0906 Sprinkler (JOI22_sprinkler) C++14
9 / 100
 1283 ms 115980 KB 
#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define pb push_back
#define pll pair<ll, ll>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define repa(a,b) for(auto a:b)
#define endl "\n"

using namespace std;

const int lim=2e5+5;
vector<int> adj[lim];
int sz[lim], h[lim][20], pos[lim], sum[20], lvl[lim], mx[lim];
pll par[lim];
ll L, H[lim];
bool vis[lim], vis2[lim][20];

struct segtree {
    int n;
    vector<ll> tree;
    segtree() {
        n = lim;
        tree.assign(2 * n, 1);
    }
    void update(int l, int r, ll value) {
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) tree[l] = (tree[l] * value) % L, l++;
            if (r & 1) --r, tree[r] = (tree[r] * value) % L;
        }
    }
    ll query(int pos) {
        ll res = 1;
        for (pos += n; pos > 0; pos >>= 1) {
            res = (res * tree[pos]) % L;
        }
        return res;
    }
} ST[20];

void sztree(int u, int p=0){
        sz[u]=1;
        repa(v,adj[u]){
                if(v==p || vis[v]) continue;
                sztree(v,u);
                sz[u]+=sz[v];
        }
}

void dis(int u, int l){
        int x=0, d=0;
        queue<int> q;
        q.push(u);
        q.push(0);
        h[u][l]=0;
        vis2[u][l]=true;
        while(q.size()){
                x=q.front();
                q.pop();
                d=q.front();
                q.pop();
                repa(y,adj[x]){
                        if(!vis2[y][l] && !vis[y]){
                                h[y][lvl[u]]=d+1;
                                q.push(y);
                                q.push(d+1);
                                vis2[y][l]=true;
                        }
                }
        }
        pos[u]=sum[l];
        sum[l]+=d+1;
        mx[u]=d;
}

pll find_centroid(int u, int p, int r){
        repa(v,adj[u]){
                if(v==p || vis[v]) continue;
                if(sz[v]>sz[r]/2){
                        pll x=find_centroid(v,u,r);
                        return {x.fi,x.se+1};
                }
        }
        return {u,0};
}

void centroid(int u, int p=0, int l=0){
        sztree(u);
        pll x=find_centroid(u,p,u);
        u=x.fi;
        lvl[u]=l;
        par[u]={p,x.se+1};
        dis(u,l);
        vis[u]=true;
        repa(v,adj[u]) if(!vis[v]) centroid(v,u,l+1);
}

void update(int u, int d, ll w){
        pll x=par[u];
        //if(!x.fi && d==2) H[u]=(H[u]*w)%L;
        while(x.fi){
                if(h[u][lvl[x.fi]]<=d) ST[lvl[x.fi]].update(pos[x.fi],pos[x.fi]+min(d-h[u][lvl[x.fi]],mx[x.fi]),w);
                x={par[x.fi].fi,par[x.fi].se+x.se};
        }
        ST[lvl[u]].update(pos[u]+(d==2),pos[u]+min(d,mx[u]),w);
}

ll query(int u){
        pll x={u,0};
        ll ans=H[u];
        while(x.fi){
                ans*=ST[lvl[x.fi]].query(pos[x.fi]+h[u][lvl[x.fi]]);
                ans%=L;
                x=par[x.fi];
        }
        return ans;
}

int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        ll n, m, u, v;
        cin>>n>>L;
        rep(i,1,n){
                cin>>u>>v;
                adj[u].pb(v);
                adj[v].pb(u);
        }
        rep(i,0,n) cin>>H[i+1];
        centroid(u);
        int q;
        cin>>q;
        while(q--){
                ll t, x, d, w;
                cin>>t;
                if(t&1){
                        cin>>x>>d>>w;
                        update(x,d,w);
                }else{
                        cin>>x;
                        cout<<query(x)<<endl;
                }
        }
}

Compilation message

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:125:15: warning: unused variable 'm' [-Wunused-variable]
  125 |         ll n, m, u, v;
      |               ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 78684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 78684 KB Output is correct
2 Correct 737 ms 105224 KB Output is correct
3 Correct 493 ms 101972 KB Output is correct
4 Correct 1032 ms 115924 KB Output is correct
5 Correct 529 ms 103760 KB Output is correct
6 Correct 446 ms 103676 KB Output is correct
7 Correct 391 ms 103940 KB Output is correct
8 Correct 242 ms 104432 KB Output is correct
9 Correct 1283 ms 114768 KB Output is correct
10 Correct 653 ms 110676 KB Output is correct
11 Correct 673 ms 105236 KB Output is correct
12 Correct 446 ms 101972 KB Output is correct
13 Correct 207 ms 103624 KB Output is correct
14 Correct 212 ms 103424 KB Output is correct
15 Correct 228 ms 103168 KB Output is correct
16 Correct 248 ms 102996 KB Output is correct
17 Correct 278 ms 103360 KB Output is correct
18 Correct 20 ms 78680 KB Output is correct
19 Correct 20 ms 78680 KB Output is correct
20 Correct 20 ms 78676 KB Output is correct
21 Correct 23 ms 78684 KB Output is correct
22 Correct 20 ms 78684 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 78684 KB Output is correct
2 Correct 737 ms 105224 KB Output is correct
3 Correct 493 ms 101972 KB Output is correct
4 Correct 1032 ms 115924 KB Output is correct
5 Correct 529 ms 103760 KB Output is correct
6 Correct 446 ms 103676 KB Output is correct
7 Correct 391 ms 103940 KB Output is correct
8 Correct 242 ms 104432 KB Output is correct
9 Correct 1283 ms 114768 KB Output is correct
10 Correct 653 ms 110676 KB Output is correct
11 Correct 673 ms 105236 KB Output is correct
12 Correct 446 ms 101972 KB Output is correct
13 Correct 207 ms 103624 KB Output is correct
14 Correct 212 ms 103424 KB Output is correct
15 Correct 228 ms 103168 KB Output is correct
16 Correct 248 ms 102996 KB Output is correct
17 Correct 278 ms 103360 KB Output is correct
18 Correct 20 ms 78680 KB Output is correct
19 Correct 20 ms 78680 KB Output is correct
20 Correct 20 ms 78676 KB Output is correct
21 Correct 23 ms 78684 KB Output is correct
22 Correct 20 ms 78684 KB Output is correct
23 Correct 20 ms 78684 KB Output is correct
24 Incorrect 660 ms 105364 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 78684 KB Output is correct
2 Correct 1188 ms 111096 KB Output is correct
3 Correct 739 ms 115980 KB Output is correct
4 Correct 955 ms 112468 KB Output is correct
5 Correct 572 ms 102392 KB Output is correct
6 Correct 465 ms 102404 KB Output is correct
7 Correct 435 ms 102536 KB Output is correct
8 Correct 215 ms 102804 KB Output is correct
9 Correct 1277 ms 115788 KB Output is correct
10 Correct 751 ms 115792 KB Output is correct
11 Correct 698 ms 102488 KB Output is correct
12 Correct 496 ms 101900 KB Output is correct
13 Correct 320 ms 102740 KB Output is correct
14 Correct 367 ms 102952 KB Output is correct
15 Correct 19 ms 78680 KB Output is correct
16 Correct 19 ms 78684 KB Output is correct
17 Correct 19 ms 78844 KB Output is correct
18 Correct 19 ms 78680 KB Output is correct
19 Incorrect 19 ms 78684 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 78684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 78684 KB Output isn't correct
2 Halted 0 ms 0 KB -