oj.uz

Submission #999553

# Submission time Handle Problem Language Result Execution time Memory
999553 2024-06-15T19:03:27 Z Saul0906 Sprinkler (JOI22_sprinkler) C++14
21 / 100
 1179 ms 116040 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 19 ms 78672 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 20 ms 78680 KB Output is correct
2 Correct 637 ms 105372 KB Output is correct
3 Correct 416 ms 102068 KB Output is correct
4 Correct 905 ms 115980 KB Output is correct
5 Correct 543 ms 103760 KB Output is correct
6 Correct 414 ms 103672 KB Output is correct
7 Correct 382 ms 104148 KB Output is correct
8 Correct 227 ms 104364 KB Output is correct
9 Correct 1141 ms 114752 KB Output is correct
10 Correct 629 ms 110672 KB Output is correct
11 Correct 670 ms 105164 KB Output is correct
12 Correct 421 ms 101968 KB Output is correct
13 Correct 188 ms 103624 KB Output is correct
14 Correct 197 ms 103368 KB Output is correct
15 Correct 230 ms 103168 KB Output is correct
16 Correct 223 ms 103008 KB Output is correct
17 Correct 250 ms 103356 KB Output is correct
18 Correct 19 ms 78684 KB Output is correct
19 Correct 19 ms 78692 KB Output is correct
20 Correct 19 ms 78684 KB Output is correct
21 Correct 20 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 20 ms 78680 KB Output is correct
2 Correct 637 ms 105372 KB Output is correct
3 Correct 416 ms 102068 KB Output is correct
4 Correct 905 ms 115980 KB Output is correct
5 Correct 543 ms 103760 KB Output is correct
6 Correct 414 ms 103672 KB Output is correct
7 Correct 382 ms 104148 KB Output is correct
8 Correct 227 ms 104364 KB Output is correct
9 Correct 1141 ms 114752 KB Output is correct
10 Correct 629 ms 110672 KB Output is correct
11 Correct 670 ms 105164 KB Output is correct
12 Correct 421 ms 101968 KB Output is correct
13 Correct 188 ms 103624 KB Output is correct
14 Correct 197 ms 103368 KB Output is correct
15 Correct 230 ms 103168 KB Output is correct
16 Correct 223 ms 103008 KB Output is correct
17 Correct 250 ms 103356 KB Output is correct
18 Correct 19 ms 78684 KB Output is correct
19 Correct 19 ms 78692 KB Output is correct
20 Correct 19 ms 78684 KB Output is correct
21 Correct 20 ms 78684 KB Output is correct
22 Correct 20 ms 78684 KB Output is correct
23 Correct 20 ms 78680 KB Output is correct
24 Incorrect 642 ms 105300 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 78684 KB Output is correct
2 Correct 1169 ms 111004 KB Output is correct
3 Correct 750 ms 116040 KB Output is correct
4 Correct 941 ms 112432 KB Output is correct
5 Correct 550 ms 102088 KB Output is correct
6 Correct 467 ms 102408 KB Output is correct
7 Correct 395 ms 102536 KB Output is correct
8 Correct 218 ms 102884 KB Output is correct
9 Correct 1179 ms 115712 KB Output is correct
10 Correct 686 ms 115628 KB Output is correct
11 Correct 658 ms 102428 KB Output is correct
12 Correct 514 ms 101716 KB Output is correct
13 Correct 326 ms 102740 KB Output is correct
14 Correct 320 ms 102948 KB Output is correct
15 Correct 20 ms 78680 KB Output is correct
16 Correct 20 ms 78684 KB Output is correct
17 Correct 21 ms 78656 KB Output is correct
18 Correct 19 ms 78684 KB Output is correct
19 Correct 20 ms 78684 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

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