oj.uz

Submission #925925

# Submission time Handle Problem Language Result Execution time Memory
925925 2024-02-12T10:49:00 Z andrei_boaca Sprinkler (JOI22_sprinkler) C++17
100 / 100
 3776 ms 1048576 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
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];
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);
    int q;
    cin>>q;
    while(q--)
    {
        int tip;
        cin>>tip;
        if(tip==1)
        {
            int nod,d,val;
            cin>>nod>>d>>val;
            update(1,nod,40-d+1,1,val);
            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();
                    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 99 ms 413492 KB Output is correct
2 Correct 88 ms 413604 KB Output is correct
3 Correct 87 ms 413520 KB Output is correct
4 Correct 95 ms 416080 KB Output is correct
5 Correct 98 ms 416124 KB Output is correct
6 Correct 94 ms 416340 KB Output is correct
7 Correct 94 ms 416448 KB Output is correct
8 Correct 93 ms 416592 KB Output is correct
9 Correct 98 ms 413512 KB Output is correct
10 Correct 87 ms 413516 KB Output is correct
11 Correct 90 ms 413500 KB Output is correct
12 Correct 87 ms 413524 KB Output is correct
13 Correct 88 ms 413520 KB Output is correct
14 Correct 89 ms 413520 KB Output is correct
15 Correct 89 ms 413520 KB Output is correct
16 Correct 89 ms 413528 KB Output is correct
17 Correct 87 ms 413576 KB Output is correct
18 Correct 89 ms 413644 KB Output is correct
19 Correct 87 ms 413524 KB Output is correct
20 Correct 89 ms 413828 KB Output is correct
21 Correct 88 ms 413620 KB Output is correct
22 Correct 89 ms 413520 KB Output is correct
23 Correct 132 ms 413524 KB Output is correct
24 Correct 89 ms 413524 KB Output is correct
25 Correct 91 ms 413416 KB Output is correct
26 Correct 87 ms 413388 KB Output is correct
27 Correct 89 ms 413448 KB Output is correct
28 Correct 89 ms 413524 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 413608 KB Output is correct
2 Correct 3453 ms 957464 KB Output is correct
3 Correct 2559 ms 960752 KB Output is correct
4 Correct 2475 ms 959464 KB Output is correct
5 Correct 3019 ms 961336 KB Output is correct
6 Correct 2308 ms 970592 KB Output is correct
7 Correct 2340 ms 979712 KB Output is correct
8 Correct 1205 ms 1011380 KB Output is correct
9 Correct 2697 ms 965196 KB Output is correct
10 Correct 2267 ms 962808 KB Output is correct
11 Correct 3222 ms 962232 KB Output is correct
12 Correct 2573 ms 961292 KB Output is correct
13 Correct 1315 ms 1004888 KB Output is correct
14 Correct 1309 ms 1005028 KB Output is correct
15 Correct 1660 ms 1005784 KB Output is correct
16 Correct 1743 ms 1013296 KB Output is correct
17 Correct 1597 ms 1030212 KB Output is correct
18 Correct 88 ms 413516 KB Output is correct
19 Correct 90 ms 413620 KB Output is correct
20 Correct 89 ms 413516 KB Output is correct
21 Correct 87 ms 413524 KB Output is correct
22 Correct 87 ms 413652 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 413608 KB Output is correct
2 Correct 3453 ms 957464 KB Output is correct
3 Correct 2559 ms 960752 KB Output is correct
4 Correct 2475 ms 959464 KB Output is correct
5 Correct 3019 ms 961336 KB Output is correct
6 Correct 2308 ms 970592 KB Output is correct
7 Correct 2340 ms 979712 KB Output is correct
8 Correct 1205 ms 1011380 KB Output is correct
9 Correct 2697 ms 965196 KB Output is correct
10 Correct 2267 ms 962808 KB Output is correct
11 Correct 3222 ms 962232 KB Output is correct
12 Correct 2573 ms 961292 KB Output is correct
13 Correct 1315 ms 1004888 KB Output is correct
14 Correct 1309 ms 1005028 KB Output is correct
15 Correct 1660 ms 1005784 KB Output is correct
16 Correct 1743 ms 1013296 KB Output is correct
17 Correct 1597 ms 1030212 KB Output is correct
18 Correct 88 ms 413516 KB Output is correct
19 Correct 90 ms 413620 KB Output is correct
20 Correct 89 ms 413516 KB Output is correct
21 Correct 87 ms 413524 KB Output is correct
22 Correct 87 ms 413652 KB Output is correct
23 Correct 88 ms 413520 KB Output is correct
24 Correct 3296 ms 961728 KB Output is correct
25 Correct 2576 ms 960656 KB Output is correct
26 Correct 2385 ms 963768 KB Output is correct
27 Correct 2879 ms 961460 KB Output is correct
28 Correct 2336 ms 970308 KB Output is correct
29 Correct 2252 ms 979228 KB Output is correct
30 Correct 1203 ms 1011664 KB Output is correct
31 Correct 2711 ms 960536 KB Output is correct
32 Correct 2251 ms 962648 KB Output is correct
33 Correct 3251 ms 961876 KB Output is correct
34 Correct 2506 ms 960700 KB Output is correct
35 Correct 88 ms 413856 KB Output is correct
36 Correct 87 ms 413480 KB Output is correct
37 Correct 87 ms 413632 KB Output is correct
38 Correct 88 ms 413640 KB Output is correct
39 Correct 92 ms 413524 KB Output is correct
40 Correct 88 ms 413520 KB Output is correct
41 Correct 90 ms 413524 KB Output is correct
42 Correct 89 ms 413520 KB Output is correct
43 Correct 87 ms 413520 KB Output is correct
44 Correct 88 ms 413640 KB Output is correct
45 Correct 87 ms 413384 KB Output is correct
46 Correct 89 ms 413520 KB Output is correct
47 Correct 88 ms 413628 KB Output is correct
48 Correct 93 ms 413524 KB Output is correct
49 Correct 88 ms 413524 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 413560 KB Output is correct
2 Correct 2673 ms 957912 KB Output is correct
3 Correct 2835 ms 959292 KB Output is correct
4 Correct 2649 ms 959532 KB Output is correct
5 Correct 3257 ms 959472 KB Output is correct
6 Correct 2504 ms 968296 KB Output is correct
7 Correct 2265 ms 977756 KB Output is correct
8 Correct 1376 ms 1009692 KB Output is correct
9 Correct 2686 ms 958140 KB Output is correct
10 Correct 2727 ms 961224 KB Output is correct
11 Correct 3465 ms 959260 KB Output is correct
12 Correct 3698 ms 959448 KB Output is correct
13 Correct 2867 ms 1026516 KB Output is correct
14 Correct 3187 ms 1048576 KB Output is correct
15 Correct 88 ms 413524 KB Output is correct
16 Correct 88 ms 413412 KB Output is correct
17 Correct 89 ms 413528 KB Output is correct
18 Correct 87 ms 413524 KB Output is correct
19 Correct 88 ms 413524 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 413780 KB Output is correct
2 Correct 2748 ms 955436 KB Output is correct
3 Correct 2766 ms 955556 KB Output is correct
4 Correct 2614 ms 958136 KB Output is correct
5 Correct 3387 ms 960664 KB Output is correct
6 Correct 2510 ms 969768 KB Output is correct
7 Correct 2477 ms 979064 KB Output is correct
8 Correct 1380 ms 1010284 KB Output is correct
9 Correct 2740 ms 963748 KB Output is correct
10 Correct 2787 ms 961544 KB Output is correct
11 Correct 3449 ms 961748 KB Output is correct
12 Correct 3557 ms 960080 KB Output is correct
13 Correct 2901 ms 1017268 KB Output is correct
14 Correct 3080 ms 1048576 KB Output is correct
15 Correct 88 ms 413524 KB Output is correct
16 Correct 86 ms 413612 KB Output is correct
17 Correct 87 ms 413520 KB Output is correct
18 Correct 87 ms 413524 KB Output is correct
19 Correct 89 ms 413784 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 413492 KB Output is correct
2 Correct 88 ms 413604 KB Output is correct
3 Correct 87 ms 413520 KB Output is correct
4 Correct 95 ms 416080 KB Output is correct
5 Correct 98 ms 416124 KB Output is correct
6 Correct 94 ms 416340 KB Output is correct
7 Correct 94 ms 416448 KB Output is correct
8 Correct 93 ms 416592 KB Output is correct
9 Correct 98 ms 413512 KB Output is correct
10 Correct 87 ms 413516 KB Output is correct
11 Correct 90 ms 413500 KB Output is correct
12 Correct 87 ms 413524 KB Output is correct
13 Correct 88 ms 413520 KB Output is correct
14 Correct 89 ms 413520 KB Output is correct
15 Correct 89 ms 413520 KB Output is correct
16 Correct 89 ms 413528 KB Output is correct
17 Correct 87 ms 413576 KB Output is correct
18 Correct 89 ms 413644 KB Output is correct
19 Correct 87 ms 413524 KB Output is correct
20 Correct 89 ms 413828 KB Output is correct
21 Correct 88 ms 413620 KB Output is correct
22 Correct 89 ms 413520 KB Output is correct
23 Correct 132 ms 413524 KB Output is correct
24 Correct 89 ms 413524 KB Output is correct
25 Correct 91 ms 413416 KB Output is correct
26 Correct 87 ms 413388 KB Output is correct
27 Correct 89 ms 413448 KB Output is correct
28 Correct 89 ms 413524 KB Output is correct
29 Correct 95 ms 413608 KB Output is correct
30 Correct 3453 ms 957464 KB Output is correct
31 Correct 2559 ms 960752 KB Output is correct
32 Correct 2475 ms 959464 KB Output is correct
33 Correct 3019 ms 961336 KB Output is correct
34 Correct 2308 ms 970592 KB Output is correct
35 Correct 2340 ms 979712 KB Output is correct
36 Correct 1205 ms 1011380 KB Output is correct
37 Correct 2697 ms 965196 KB Output is correct
38 Correct 2267 ms 962808 KB Output is correct
39 Correct 3222 ms 962232 KB Output is correct
40 Correct 2573 ms 961292 KB Output is correct
41 Correct 1315 ms 1004888 KB Output is correct
42 Correct 1309 ms 1005028 KB Output is correct
43 Correct 1660 ms 1005784 KB Output is correct
44 Correct 1743 ms 1013296 KB Output is correct
45 Correct 1597 ms 1030212 KB Output is correct
46 Correct 88 ms 413516 KB Output is correct
47 Correct 90 ms 413620 KB Output is correct
48 Correct 89 ms 413516 KB Output is correct
49 Correct 87 ms 413524 KB Output is correct
50 Correct 87 ms 413652 KB Output is correct
51 Correct 88 ms 413520 KB Output is correct
52 Correct 3296 ms 961728 KB Output is correct
53 Correct 2576 ms 960656 KB Output is correct
54 Correct 2385 ms 963768 KB Output is correct
55 Correct 2879 ms 961460 KB Output is correct
56 Correct 2336 ms 970308 KB Output is correct
57 Correct 2252 ms 979228 KB Output is correct
58 Correct 1203 ms 1011664 KB Output is correct
59 Correct 2711 ms 960536 KB Output is correct
60 Correct 2251 ms 962648 KB Output is correct
61 Correct 3251 ms 961876 KB Output is correct
62 Correct 2506 ms 960700 KB Output is correct
63 Correct 88 ms 413856 KB Output is correct
64 Correct 87 ms 413480 KB Output is correct
65 Correct 87 ms 413632 KB Output is correct
66 Correct 88 ms 413640 KB Output is correct
67 Correct 92 ms 413524 KB Output is correct
68 Correct 88 ms 413520 KB Output is correct
69 Correct 90 ms 413524 KB Output is correct
70 Correct 89 ms 413520 KB Output is correct
71 Correct 87 ms 413520 KB Output is correct
72 Correct 88 ms 413640 KB Output is correct
73 Correct 87 ms 413384 KB Output is correct
74 Correct 89 ms 413520 KB Output is correct
75 Correct 88 ms 413628 KB Output is correct
76 Correct 93 ms 413524 KB Output is correct
77 Correct 88 ms 413524 KB Output is correct
78 Correct 89 ms 413560 KB Output is correct
79 Correct 2673 ms 957912 KB Output is correct
80 Correct 2835 ms 959292 KB Output is correct
81 Correct 2649 ms 959532 KB Output is correct
82 Correct 3257 ms 959472 KB Output is correct
83 Correct 2504 ms 968296 KB Output is correct
84 Correct 2265 ms 977756 KB Output is correct
85 Correct 1376 ms 1009692 KB Output is correct
86 Correct 2686 ms 958140 KB Output is correct
87 Correct 2727 ms 961224 KB Output is correct
88 Correct 3465 ms 959260 KB Output is correct
89 Correct 3698 ms 959448 KB Output is correct
90 Correct 2867 ms 1026516 KB Output is correct
91 Correct 3187 ms 1048576 KB Output is correct
92 Correct 88 ms 413524 KB Output is correct
93 Correct 88 ms 413412 KB Output is correct
94 Correct 89 ms 413528 KB Output is correct
95 Correct 87 ms 413524 KB Output is correct
96 Correct 88 ms 413524 KB Output is correct
97 Correct 89 ms 413780 KB Output is correct
98 Correct 2748 ms 955436 KB Output is correct
99 Correct 2766 ms 955556 KB Output is correct
100 Correct 2614 ms 958136 KB Output is correct
101 Correct 3387 ms 960664 KB Output is correct
102 Correct 2510 ms 969768 KB Output is correct
103 Correct 2477 ms 979064 KB Output is correct
104 Correct 1380 ms 1010284 KB Output is correct
105 Correct 2740 ms 963748 KB Output is correct
106 Correct 2787 ms 961544 KB Output is correct
107 Correct 3449 ms 961748 KB Output is correct
108 Correct 3557 ms 960080 KB Output is correct
109 Correct 2901 ms 1017268 KB Output is correct
110 Correct 3080 ms 1048576 KB Output is correct
111 Correct 88 ms 413524 KB Output is correct
112 Correct 86 ms 413612 KB Output is correct
113 Correct 87 ms 413520 KB Output is correct
114 Correct 87 ms 413524 KB Output is correct
115 Correct 89 ms 413784 KB Output is correct
116 Correct 3340 ms 964176 KB Output is correct
117 Correct 3534 ms 967180 KB Output is correct
118 Correct 2665 ms 968548 KB Output is correct
119 Correct 3234 ms 966028 KB Output is correct
120 Correct 2549 ms 974696 KB Output is correct
121 Correct 2378 ms 984760 KB Output is correct
122 Correct 1395 ms 1016508 KB Output is correct
123 Correct 2827 ms 966188 KB Output is correct
124 Correct 2863 ms 963448 KB Output is correct
125 Correct 3458 ms 965052 KB Output is correct
126 Correct 3729 ms 966452 KB Output is correct
127 Correct 3776 ms 966948 KB Output is correct
128 Correct 3073 ms 1029344 KB Output is correct
129 Correct 3254 ms 1048576 KB Output is correct