oj.uz

Submission #876842

# Submission time Handle Problem Language Result Execution time Memory
876842 2023-11-22T12:25:14 Z simona1230 Sprinkler (JOI22_sprinkler) C++17
12 / 100
 1426 ms 98928 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 12380 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 2 ms 12216 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 5 ms 12380 KB Output is correct
2 Correct 1182 ms 91020 KB Output is correct
3 Correct 600 ms 87976 KB Output is correct
4 Correct 984 ms 94800 KB Output is correct
5 Correct 881 ms 89700 KB Output is correct
6 Correct 740 ms 89428 KB Output is correct
7 Correct 865 ms 89856 KB Output is correct
8 Correct 649 ms 90028 KB Output is correct
9 Correct 1181 ms 98928 KB Output is correct
10 Correct 650 ms 95432 KB Output is correct
11 Incorrect 1110 ms 91140 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12380 KB Output is correct
2 Correct 1182 ms 91020 KB Output is correct
3 Correct 600 ms 87976 KB Output is correct
4 Correct 984 ms 94800 KB Output is correct
5 Correct 881 ms 89700 KB Output is correct
6 Correct 740 ms 89428 KB Output is correct
7 Correct 865 ms 89856 KB Output is correct
8 Correct 649 ms 90028 KB Output is correct
9 Correct 1181 ms 98928 KB Output is correct
10 Correct 650 ms 95432 KB Output is correct
11 Incorrect 1110 ms 91140 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 1252 ms 96280 KB Output is correct
3 Correct 947 ms 93352 KB Output is correct
4 Correct 994 ms 94180 KB Output is correct
5 Correct 880 ms 88188 KB Output is correct
6 Correct 739 ms 88384 KB Output is correct
7 Correct 798 ms 88424 KB Output is correct
8 Correct 650 ms 88944 KB Output is correct
9 Correct 1276 ms 93920 KB Output is correct
10 Correct 962 ms 95000 KB Output is correct
11 Correct 1426 ms 88420 KB Output is correct
12 Correct 714 ms 87688 KB Output is correct
13 Correct 590 ms 88780 KB Output is correct
14 Correct 631 ms 89252 KB Output is correct
15 Correct 3 ms 12380 KB Output is correct
16 Correct 3 ms 12380 KB Output is correct
17 Correct 3 ms 12380 KB Output is correct
18 Correct 4 ms 12376 KB Output is correct
19 Correct 3 ms 12380 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12380 KB Output is correct
2 Incorrect 1290 ms 96040 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 12380 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 2 ms 12216 KB Output is correct
4 Incorrect 4 ms 12380 KB Output isn't correct
5 Halted 0 ms 0 KB -