oj.uz

Submission #876839

# Submission time Handle Problem Language Result Execution time Memory
876839 2023-11-22T12:23:52 Z simona1230 Sprinkler (JOI22_sprinkler) C++17
12 / 100
 1400 ms 107004 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;
    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 3 ms 12380 KB Output is correct
2 Correct 3 ms 12380 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Incorrect 4 ms 12380 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 1123 ms 95488 KB Output is correct
3 Correct 638 ms 99688 KB Output is correct
4 Correct 921 ms 104444 KB Output is correct
5 Correct 951 ms 99812 KB Output is correct
6 Correct 736 ms 99032 KB Output is correct
7 Correct 758 ms 99816 KB Output is correct
8 Correct 689 ms 100216 KB Output is correct
9 Correct 1320 ms 107004 KB Output is correct
10 Correct 661 ms 106916 KB Output is correct
11 Incorrect 1152 ms 99140 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 1123 ms 95488 KB Output is correct
3 Correct 638 ms 99688 KB Output is correct
4 Correct 921 ms 104444 KB Output is correct
5 Correct 951 ms 99812 KB Output is correct
6 Correct 736 ms 99032 KB Output is correct
7 Correct 758 ms 99816 KB Output is correct
8 Correct 689 ms 100216 KB Output is correct
9 Correct 1320 ms 107004 KB Output is correct
10 Correct 661 ms 106916 KB Output is correct
11 Incorrect 1152 ms 99140 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 1294 ms 100712 KB Output is correct
3 Correct 941 ms 102828 KB Output is correct
4 Correct 975 ms 102792 KB Output is correct
5 Correct 961 ms 96736 KB Output is correct
6 Correct 768 ms 96800 KB Output is correct
7 Correct 801 ms 96988 KB Output is correct
8 Correct 671 ms 97152 KB Output is correct
9 Correct 1400 ms 101712 KB Output is correct
10 Correct 1071 ms 103972 KB Output is correct
11 Correct 1236 ms 96092 KB Output is correct
12 Correct 892 ms 97116 KB Output is correct
13 Correct 613 ms 98000 KB Output is correct
14 Correct 664 ms 98808 KB Output is correct
15 Correct 4 ms 12380 KB Output is correct
16 Correct 4 ms 12380 KB Output is correct
17 Correct 4 ms 12380 KB Output is correct
18 Correct 4 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 12392 KB Output is correct
2 Incorrect 1332 ms 100328 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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