oj.uz

Submission #925909

# Submission time Handle Problem Language Result Execution time Memory
925909 2024-02-12T10:36:03 Z andrei_boaca Sprinkler (JOI22_sprinkler) C++17
3 / 100
 3829 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;
int n,mod,h[200005],root;
vector<int> muchii[200005];
vector<int> kids[200005];
int d1[200005],dp[21][200005],in[200005],out[200005],timp;
int use[200005],parent[200005],par[200005];
int nr[200005],where[200005];
int add[200005][41];
vector<int> aib[2][200005][41];   /// 0 -> pref, 1 -> suf
bool isancestor(int a,int b)
{
    return in[a]<=in[b]&&out[a]>=out[b];
}
int LCA(int a,int b)
{
    if(d1[a]>d1[b])
        swap(a,b);
    if(isancestor(a,b))
        return a;
    for(int i=18;i>=0;i--)
        if(dp[i][a]!=0&&!isancestor(dp[i][a],b))
            a=dp[i][a];
    return dp[0][a];
}
int dist(int a,int b)
{
    int lca=LCA(a,b);
    return d1[a]+d1[b]-2*d1[lca];
}
void build(int nod)
{
    timp++;
    in[nod]=timp;
    for(int i=1;i<=20;i++)
        dp[i][nod]=dp[i-1][dp[i-1][nod]];
    for(int i:muchii[nod])
        if(i!=dp[0][nod])
        {
            dp[0][i]=nod;
            d1[i]=d1[nod]+1;
            build(i);
        }
    out[nod]=timp;
}
void dfs1(int nod)
{
    nr[nod]=1;
    for(int i:muchii[nod])
        if(!use[i]&&i!=par[nod])
        {
            par[i]=nod;
            dfs1(i);
            nr[nod]+=nr[i];
        }
}
int centroid(int nod)
{
    par[nod]=0;
    dfs1(nod);
    int lg=nr[nod];
    int r=nod;
    while(true)
    {
        bool bad=0;
        for(int i:muchii[r])
            if(!use[i]&&par[i]==r&&nr[i]>lg/2)
            {
                bad=1;
                par[r]=i;
                par[i]=0;
                nr[r]-=nr[i];
                nr[i]+=nr[r];
                r=i;
                break;
            }
        if(!bad)
            break;
    }
    use[r]=1;
    for(int i:muchii[r])
        if(!use[i])
        {
            int x=centroid(i);
            kids[r].push_back(x);
        }
    return r;
}
void dfs(int nod)
{
    int cnt=0;
    for(int i:kids[nod])
    {
        cnt++;
        where[i]=cnt;
        par[i]=nod;
        dfs(i);
    }
    int lg=kids[nod].size();
    for(int i=0;i<=1;i++)
        for(int j=0;j<=40;j++)
            for(int k=0;k<=lg;k++)
                aib[i][nod][j].push_back(1);
}
int lsb(int x)
{
    return x&(-x);
}
void update(int ind,int cur,int p1,int p2,int val)
{
    int lg=kids[cur].size();
    for(int i=p1;i<=40;i+=lsb(i))
        for(int j=p2;j<=lg;j+=lsb(j))
            aib[ind][cur][i][j]=(1LL*aib[ind][cur][i][j]*val)%mod;
}
int query(int ind,int cur,int p1,int p2)
{
    int rez=1;
    for(int i=p1;i>=1;i-=lsb(i))
        for(int j=p2;j>=1;j-=lsb(j))
            rez=(1LL*rez*aib[ind][cur][i][j])%mod;
    return rez;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>mod;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        cin>>h[i];
    d1[1]=0;
    build(1);
    root=centroid(1);
    par[root]=0;
    dfs(root);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=40;j++)
            add[i][j]=1;
    int q;
    cin>>q;
    while(q--)
    {
        int tip;
        cin>>tip;
        if(tip==1)
        {
            int nod,d,val;
            cin>>nod>>d>>val;
            for(int i=1;i<=d;i++)
                add[nod][i]=(1LL*add[nod][i]*val)%mod;
            int cur=nod;
            int badind=0;
            while(cur!=0)
            {
                int dmax=d-dist(nod,cur);
                if(dmax>=0)
                    h[cur]=(1LL*h[cur]*val)%mod;
                if(dmax>0&&badind!=0)
                {
                    int lg=kids[cur].size();
                    update(1,cur,40-dmax+1,badind+1,val);
                    update(0,cur,40-dmax+1,lg-badind+2,val);
                }
                badind=where[cur];
                cur=par[cur];
            }
        }
        if(tip==2)
        {
            int nod;
            cin>>nod;
            int ans=h[nod];
            int badind=where[nod];
            int cur=par[nod];
            while(cur!=0)
            {
                int d=dist(nod,cur);
                if(d<=40)
                {
                    int lg=kids[cur].size();
                    ans=(1LL*ans*add[cur][d])%mod;
                    int val=query(1,cur,40-d+1,badind);
                    ans=(1LL*ans*val)%mod;
                    val=query(0,cur,40-d+1,lg-badind+1);
                    ans=(1LL*ans*val)%mod;
                }
                badind=where[cur];
                cur=par[cur];
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 417112 KB Output is correct
2 Correct 93 ms 417212 KB Output is correct
3 Correct 88 ms 417108 KB Output is correct
4 Correct 94 ms 419864 KB Output is correct
5 Correct 95 ms 419924 KB Output is correct
6 Correct 97 ms 419964 KB Output is correct
7 Correct 99 ms 420180 KB Output is correct
8 Correct 93 ms 420176 KB Output is correct
9 Correct 89 ms 416972 KB Output is correct
10 Correct 89 ms 417216 KB Output is correct
11 Correct 89 ms 417424 KB Output is correct
12 Correct 87 ms 417236 KB Output is correct
13 Correct 90 ms 417108 KB Output is correct
14 Correct 87 ms 417292 KB Output is correct
15 Correct 88 ms 417108 KB Output is correct
16 Correct 87 ms 417104 KB Output is correct
17 Correct 88 ms 417104 KB Output is correct
18 Correct 88 ms 417140 KB Output is correct
19 Correct 89 ms 417104 KB Output is correct
20 Correct 88 ms 417204 KB Output is correct
21 Correct 89 ms 417104 KB Output is correct
22 Correct 88 ms 417104 KB Output is correct
23 Correct 89 ms 417104 KB Output is correct
24 Correct 89 ms 417360 KB Output is correct
25 Correct 88 ms 417212 KB Output is correct
26 Correct 88 ms 417108 KB Output is correct
27 Correct 89 ms 417180 KB Output is correct
28 Correct 88 ms 417080 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 417020 KB Output is correct
2 Correct 3458 ms 997880 KB Output is correct
3 Correct 2393 ms 998460 KB Output is correct
4 Correct 2482 ms 994564 KB Output is correct
5 Correct 2843 ms 998668 KB Output is correct
6 Correct 2174 ms 1007148 KB Output is correct
7 Correct 2340 ms 1016960 KB Output is correct
8 Correct 1239 ms 1048516 KB Output is correct
9 Correct 2670 ms 998348 KB Output is correct
10 Correct 2185 ms 997660 KB Output is correct
11 Correct 3399 ms 998204 KB Output is correct
12 Correct 2545 ms 998584 KB Output is correct
13 Correct 1248 ms 1042300 KB Output is correct
14 Correct 1285 ms 1043012 KB Output is correct
15 Correct 1654 ms 1043556 KB Output is correct
16 Correct 1641 ms 1048576 KB Output is correct
17 Runtime error 907 ms 1048576 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 417020 KB Output is correct
2 Correct 3458 ms 997880 KB Output is correct
3 Correct 2393 ms 998460 KB Output is correct
4 Correct 2482 ms 994564 KB Output is correct
5 Correct 2843 ms 998668 KB Output is correct
6 Correct 2174 ms 1007148 KB Output is correct
7 Correct 2340 ms 1016960 KB Output is correct
8 Correct 1239 ms 1048516 KB Output is correct
9 Correct 2670 ms 998348 KB Output is correct
10 Correct 2185 ms 997660 KB Output is correct
11 Correct 3399 ms 998204 KB Output is correct
12 Correct 2545 ms 998584 KB Output is correct
13 Correct 1248 ms 1042300 KB Output is correct
14 Correct 1285 ms 1043012 KB Output is correct
15 Correct 1654 ms 1043556 KB Output is correct
16 Correct 1641 ms 1048576 KB Output is correct
17 Runtime error 907 ms 1048576 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 417128 KB Output is correct
2 Correct 2753 ms 994972 KB Output is correct
3 Correct 3000 ms 992980 KB Output is correct
4 Correct 2722 ms 993176 KB Output is correct
5 Correct 3279 ms 995760 KB Output is correct
6 Correct 2611 ms 1004820 KB Output is correct
7 Correct 2304 ms 1013844 KB Output is correct
8 Correct 1523 ms 1045648 KB Output is correct
9 Correct 2877 ms 992056 KB Output is correct
10 Correct 2999 ms 994856 KB Output is correct
11 Correct 3594 ms 995360 KB Output is correct
12 Correct 3829 ms 996200 KB Output is correct
13 Runtime error 831 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 417108 KB Output is correct
2 Correct 2849 ms 993864 KB Output is correct
3 Correct 2932 ms 990924 KB Output is correct
4 Correct 2734 ms 992296 KB Output is correct
5 Correct 3366 ms 996852 KB Output is correct
6 Correct 2718 ms 1005848 KB Output is correct
7 Correct 2550 ms 1014704 KB Output is correct
8 Correct 1564 ms 1046748 KB Output is correct
9 Correct 2775 ms 997268 KB Output is correct
10 Correct 2929 ms 995752 KB Output is correct
11 Correct 3469 ms 997980 KB Output is correct
12 Correct 3599 ms 996340 KB Output is correct
13 Runtime error 836 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 417112 KB Output is correct
2 Correct 93 ms 417212 KB Output is correct
3 Correct 88 ms 417108 KB Output is correct
4 Correct 94 ms 419864 KB Output is correct
5 Correct 95 ms 419924 KB Output is correct
6 Correct 97 ms 419964 KB Output is correct
7 Correct 99 ms 420180 KB Output is correct
8 Correct 93 ms 420176 KB Output is correct
9 Correct 89 ms 416972 KB Output is correct
10 Correct 89 ms 417216 KB Output is correct
11 Correct 89 ms 417424 KB Output is correct
12 Correct 87 ms 417236 KB Output is correct
13 Correct 90 ms 417108 KB Output is correct
14 Correct 87 ms 417292 KB Output is correct
15 Correct 88 ms 417108 KB Output is correct
16 Correct 87 ms 417104 KB Output is correct
17 Correct 88 ms 417104 KB Output is correct
18 Correct 88 ms 417140 KB Output is correct
19 Correct 89 ms 417104 KB Output is correct
20 Correct 88 ms 417204 KB Output is correct
21 Correct 89 ms 417104 KB Output is correct
22 Correct 88 ms 417104 KB Output is correct
23 Correct 89 ms 417104 KB Output is correct
24 Correct 89 ms 417360 KB Output is correct
25 Correct 88 ms 417212 KB Output is correct
26 Correct 88 ms 417108 KB Output is correct
27 Correct 89 ms 417180 KB Output is correct
28 Correct 88 ms 417080 KB Output is correct
29 Correct 88 ms 417020 KB Output is correct
30 Correct 3458 ms 997880 KB Output is correct
31 Correct 2393 ms 998460 KB Output is correct
32 Correct 2482 ms 994564 KB Output is correct
33 Correct 2843 ms 998668 KB Output is correct
34 Correct 2174 ms 1007148 KB Output is correct
35 Correct 2340 ms 1016960 KB Output is correct
36 Correct 1239 ms 1048516 KB Output is correct
37 Correct 2670 ms 998348 KB Output is correct
38 Correct 2185 ms 997660 KB Output is correct
39 Correct 3399 ms 998204 KB Output is correct
40 Correct 2545 ms 998584 KB Output is correct
41 Correct 1248 ms 1042300 KB Output is correct
42 Correct 1285 ms 1043012 KB Output is correct
43 Correct 1654 ms 1043556 KB Output is correct
44 Correct 1641 ms 1048576 KB Output is correct
45 Runtime error 907 ms 1048576 KB Execution killed with signal 9
46 Halted 0 ms 0 KB -