oj.uz

Submission #876624

# Submission time Handle Problem Language Result Execution time Memory
876624 2023-11-22T06:17:46 Z n3rm1n Sprinkler (JOI22_sprinkler) C++17
12 / 100
 600 ms 120916 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

const int MAXN = 4e5 + 10;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int n, mod;
vector < int > g[MAXN];
int h[MAXN];

void read()
{
    cin >> n >> mod;
    int xx, yy;
    for (int i = 1; i < n; ++ i)
    {
        cin >> xx >> yy;
        g[xx].push_back(yy);
        g[yy].push_back(xx);
    }
    for (int i = 1; i <= n; ++ i)
        cin >> h[i];
}

///int tin[MAXN], tout[MAXN];
int used[MAXN];
int p[MAXN];
vector < int > on_lvls[MAXN];
int timerr = 0;
void dfs(int beg, int parent, int depth)
{
   /// tin[beg] = timerr;
    p[beg] = parent;
    used[beg] = 1;
    ///on_lvls[depth].push_back(beg);
    int nb, children = 0;
    for (int i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i];
        if(!used[nb])
        {
            children ++;
            dfs(nb, beg, depth + 1);
        }
    }
    /**if(children)
    {
        timerr ++;
        tout[beg] = timerr;
    }*/
}

int x, d, w;
int upd[MAXN][88];

void print_upd()
{
    for (int i = 1; i <= n; ++ i)
    {
        cout << "upd for vertex " << i << " " << endl;
        cout << "depth : ";
        for (int j = 0; j <= 3; ++ j)
            cout << upd[i][j] << ", ";
        cout << endl;
    }
}
void update_arrays()
{
   /// cout << "***" << endl;
    int vertex = x, depth = d;
    while(vertex != 0 && depth >= 0)
    {

        upd[vertex][depth] *= w;
        upd[vertex][depth] %= mod;
        if(depth)
        {
            upd[vertex][depth-1] *= w;
            upd[vertex][depth-1] %= mod;
        }
        ///cout << vertex << " " << depth << " " << upd[vertex][depth] << endl;
        ///cout << vertex << " " << depth-1 << " " << upd[vertex][depth-1] << endl;
        vertex = p[vertex];
        depth --;
    }
   if(vertex == 0)
   {
       for (int i = 0; i <= depth; ++ i)
        {
            upd[1][i] *= w;
            upd[1][i] %= mod;
        }
   }
}
void solve_query()
{
    int anc = x, lvl_diff = 0;
    int ans = h[x];
    //cout << "solving for v = " << anc << endl;
    while(anc && lvl_diff <= 40)
    {
        //cout << "anc = " << anc << " " << "mult is " << upd[anc][lvl_diff] << endl;
        ans = ans * upd[anc][lvl_diff];
        ans %= mod;
        anc = p[anc];
        lvl_diff ++;
    }
    cout << ans << endl;
}
void queries()
{
    int q;
    cin >> q;
    int type;
    while(q --)
    {
        cin >> type;
        if(type == 1)
        {
            cin >> x >> d >> w;
            update_arrays();
            ///print_upd();
        }
        else
        {
            cin >> x;
            solve_query();
        }
    }
}
int main()
{
    speed();

    read();
    for (int i = 1; i <= n; ++ i)
        for (int j = 0; j <= 80; ++ j)
            upd[i][j] = 1;
    dfs(1, 0, 1);
    queries();
    return 0;

}

Compilation message

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

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23900 KB Output is correct
2 Correct 5 ms 24052 KB Output is correct
3 Correct 5 ms 23900 KB Output is correct
4 Incorrect 6 ms 26308 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 23900 KB Output is correct
2 Incorrect 357 ms 112012 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23900 KB Output is correct
2 Correct 527 ms 120916 KB Output is correct
3 Correct 600 ms 119324 KB Output is correct
4 Correct 474 ms 118664 KB Output is correct
5 Correct 328 ms 109216 KB Output is correct
6 Correct 276 ms 109472 KB Output is correct
7 Correct 256 ms 109796 KB Output is correct
8 Correct 201 ms 110024 KB Output is correct
9 Correct 509 ms 117504 KB Output is correct
10 Correct 588 ms 120644 KB Output is correct
11 Correct 362 ms 108956 KB Output is correct
12 Correct 403 ms 110256 KB Output is correct
13 Correct 329 ms 110672 KB Output is correct
14 Correct 333 ms 111584 KB Output is correct
15 Correct 5 ms 23896 KB Output is correct
16 Correct 5 ms 23900 KB Output is correct
17 Correct 5 ms 24052 KB Output is correct
18 Correct 5 ms 23900 KB Output is correct
19 Correct 6 ms 23900 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

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