oj.uz

Submission #899654

# Submission time Handle Problem Language Result Execution time Memory
899654 2024-01-06T19:07:52 Z alexander707070 Sprinkler (JOI22_sprinkler) C++14
9 / 100
 503 ms 170132 KB 
#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define MAXN 200007
using namespace std;

int n,q,type;
long long mod,w;
int a,b,s,d;
vector<int> v[MAXN];
int parent[MAXN];

long long mult[MAXN][42];

void dfs(int x,int p){
    parent[x]=p;

    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p)continue;
        dfs(v[x][i],x);
    }
}

void query(int x,int dist,long long p){
    if(dist==0){
        mult[x][dist]*=p;
        mult[x][dist]%=mod;
        return;
    }

    mult[x][dist]*=p;
    mult[x][dist]%=mod;

    mult[x][dist-1]*=p;
    mult[x][dist-1]%=mod;

    if(x==0)query(parent[x],dist-2,p);
    else query(parent[x],dist-1,p);
}

long long getval(int x,int dist){
    if(dist==41)return 1;

    return (mult[x][dist]*getval(parent[x],dist+1))%mod;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>mod;
    for(int i=1;i<=n-1;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(int i=0;i<=n;i++){
        for(int f=0;f<=40;f++){
            mult[i][f]=1;
        }
    }

    dfs(1,0);

    for(int i=1;i<=n;i++){
        cin>>mult[i][0];
    }

    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>type;
        if(type==1){
            cin>>s>>d>>w;
            query(s,d,w);
        }else{
            cin>>s;
            cout<<getval(s,0)<<"\n";
        }
    }

    return 0;
}

Compilation message

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

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Correct 483 ms 85996 KB Output is correct
3 Correct 301 ms 84472 KB Output is correct
4 Correct 406 ms 88272 KB Output is correct
5 Correct 365 ms 85336 KB Output is correct
6 Correct 281 ms 84876 KB Output is correct
7 Correct 290 ms 85588 KB Output is correct
8 Correct 284 ms 85884 KB Output is correct
9 Correct 503 ms 90452 KB Output is correct
10 Correct 291 ms 88660 KB Output is correct
11 Correct 467 ms 85764 KB Output is correct
12 Correct 268 ms 84540 KB Output is correct
13 Correct 170 ms 85032 KB Output is correct
14 Correct 198 ms 85128 KB Output is correct
15 Correct 197 ms 84912 KB Output is correct
16 Correct 189 ms 84888 KB Output is correct
17 Correct 222 ms 85652 KB Output is correct
18 Correct 2 ms 7900 KB Output is correct
19 Correct 2 ms 7772 KB Output is correct
20 Correct 2 ms 7772 KB Output is correct
21 Correct 2 ms 7772 KB Output is correct
22 Correct 2 ms 7908 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Correct 483 ms 85996 KB Output is correct
3 Correct 301 ms 84472 KB Output is correct
4 Correct 406 ms 88272 KB Output is correct
5 Correct 365 ms 85336 KB Output is correct
6 Correct 281 ms 84876 KB Output is correct
7 Correct 290 ms 85588 KB Output is correct
8 Correct 284 ms 85884 KB Output is correct
9 Correct 503 ms 90452 KB Output is correct
10 Correct 291 ms 88660 KB Output is correct
11 Correct 467 ms 85764 KB Output is correct
12 Correct 268 ms 84540 KB Output is correct
13 Correct 170 ms 85032 KB Output is correct
14 Correct 198 ms 85128 KB Output is correct
15 Correct 197 ms 84912 KB Output is correct
16 Correct 189 ms 84888 KB Output is correct
17 Correct 222 ms 85652 KB Output is correct
18 Correct 2 ms 7900 KB Output is correct
19 Correct 2 ms 7772 KB Output is correct
20 Correct 2 ms 7772 KB Output is correct
21 Correct 2 ms 7772 KB Output is correct
22 Correct 2 ms 7908 KB Output is correct
23 Correct 2 ms 7968 KB Output is correct
24 Correct 446 ms 85920 KB Output is correct
25 Runtime error 273 ms 164136 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7772 KB Output is correct
2 Runtime error 241 ms 170132 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7772 KB Output isn't correct
2 Halted 0 ms 0 KB -