oj.uz

Submission #876841

# Submission time Handle Problem Language Result Execution time Memory
876841 2023-11-22T12:25:13 Z simona1230 Sprinkler (JOI22_sprinkler) C++17
12 / 100
 1385 ms 99084 KB 
#include <bits/stdc++.h>
using namespace std;
long long n,l;
vector<long long> v[200001];
long long h[200001];
void read()
{
    cin>>n>>l;
    for(long long i=1;i<n;i++)
    {
        long long a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(long long i=1;i<=n;i++)
        cin>>h[i];
}
long long curr[200001][45];
long long q,t,x,d,w;
long long used[200001];
long long p[200001];
void dfs(long long i)
{
    used[i]=1;
    for(long long j=0;j<v[i].size();j++)
    {
        long long nb=v[i][j];
        if(!used[nb])
        {
            p[nb]=i;
            dfs(nb);
        }
    }
}
void upd(long long i,long long lvl)
{
    curr[i][lvl]*=w;
    curr[i][lvl]%=l;
    if(lvl>0)
    {
        curr[i][lvl-1]*=w;
        curr[i][lvl-1]%=l;
    }
    if(i==1)
    {
        for(int j=0;j<lvl;j++)
        {
            curr[i][j]*=w;
            curr[i][j]%=l;
        }
    }
    if(i!=1&&lvl!=0)
        upd(p[i],lvl-1);
}
long long get(long long i,long long lvl)
{
    long long here=curr[i][lvl];
    if(i!=1&&lvl!=40)
        here*=get(p[i],lvl+1);
    return here%l;
}
void solve()
{
    for(long long i=1;i<=n;i++)
        for(long long j=0;j<=40;j++)
            curr[i][j]=1;
    dfs(1);
    cin>>q;
    for(long long i=1;i<=q;i++)
    {
        cin>>t>>x;
        if(t==1)
        {
            cin>>d>>w;
            upd(x,d);
        }
        else
        {
            cout<<(get(x,0)*h[x])%l<<endl;
        }
    }
}
int main()
{
    read();
    solve();
    return 0;
}

Compilation message

sprinkler.cpp: In function 'void dfs(long long int)':
sprinkler.cpp:26:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(long long j=0;j<v[i].size();j++)
      |                       ~^~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12376 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 3 ms 12380 KB Output is correct
4 Incorrect 4 ms 12376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Correct 1137 ms 91164 KB Output is correct
3 Correct 608 ms 87792 KB Output is correct
4 Correct 912 ms 94252 KB Output is correct
5 Correct 871 ms 89416 KB Output is correct
6 Correct 757 ms 89344 KB Output is correct
7 Correct 843 ms 89748 KB Output is correct
8 Correct 668 ms 90044 KB Output is correct
9 Correct 1226 ms 99084 KB Output is correct
10 Correct 620 ms 95252 KB Output is correct
11 Incorrect 1093 ms 91236 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Correct 1137 ms 91164 KB Output is correct
3 Correct 608 ms 87792 KB Output is correct
4 Correct 912 ms 94252 KB Output is correct
5 Correct 871 ms 89416 KB Output is correct
6 Correct 757 ms 89344 KB Output is correct
7 Correct 843 ms 89748 KB Output is correct
8 Correct 668 ms 90044 KB Output is correct
9 Correct 1226 ms 99084 KB Output is correct
10 Correct 620 ms 95252 KB Output is correct
11 Incorrect 1093 ms 91236 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12376 KB Output is correct
2 Correct 1236 ms 96132 KB Output is correct
3 Correct 970 ms 93360 KB Output is correct
4 Correct 1008 ms 94496 KB Output is correct
5 Correct 944 ms 88244 KB Output is correct
6 Correct 751 ms 88304 KB Output is correct
7 Correct 749 ms 88164 KB Output is correct
8 Correct 707 ms 88396 KB Output is correct
9 Correct 1232 ms 93684 KB Output is correct
10 Correct 913 ms 95012 KB Output is correct
11 Correct 1385 ms 88116 KB Output is correct
12 Correct 873 ms 87636 KB Output is correct
13 Correct 585 ms 88404 KB Output is correct
14 Correct 628 ms 89344 KB Output is correct
15 Correct 4 ms 12376 KB Output is correct
16 Correct 3 ms 12380 KB Output is correct
17 Correct 3 ms 12380 KB Output is correct
18 Correct 3 ms 12380 KB Output is correct
19 Correct 4 ms 12380 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12380 KB Output is correct
2 Incorrect 1261 ms 96088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12376 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 3 ms 12380 KB Output is correct
4 Incorrect 4 ms 12376 KB Output isn't correct
5 Halted 0 ms 0 KB -