oj.uz

Submission #876625

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

const long long MAXN = 4e5 + 10;

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

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

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

///long long tin[MAXN], tout[MAXN];
long long used[MAXN];
long long p[MAXN];
vector < long long > on_lvls[MAXN];
long long timerr = 0;
void dfs(long long beg, long long parent, long long depth)
{
   /// tin[beg] = timerr;
    p[beg] = parent;
    used[beg] = 1;
    ///on_lvls[depth].push_back(beg);
    long long nb, children = 0;
    for (long long 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;
    }*/
}

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

void print_upd()
{
    for (long long i = 1; i <= n; ++ i)
    {
        cout << "upd for vertex " << i << " " << endl;
        cout << "depth : ";
        for (long long j = 0; j <= 3; ++ j)
            cout << upd[i][j] << ", ";
        cout << endl;
    }
}
void update_arrays()
{
   /// cout << "***" << endl;
    long long 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 (long long i = 0; i <= depth; ++ i)
        {
            upd[1][i] *= w;
            upd[1][i] %= mod;
        }
   }
}
void solve_query()
{
    long long anc = x, lvl_diff = 0;
    long long 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()
{
    long long q;
    cin >> q;
    long long type;
    while(q --)
    {
        cin >> type;
        if(type == 1)
        {
            cin >> x >> d >> w;
            update_arrays();
            ///prlong long_upd();
        }
        else
        {
            cin >> x;
            solve_query();
        }
    }
}
int main()
{
    speed();

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

}

Compilation message

sprinkler.cpp: In function 'void dfs(long long int, long long int, long long int)':
sprinkler.cpp:45:29: 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]
   45 |     for (long long i = 0; i < g[beg].size(); ++ i)
      |                           ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24920 KB Output is correct
2 Correct 5 ms 24924 KB Output is correct
3 Correct 5 ms 24924 KB Output is correct
4 Incorrect 6 ms 27004 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 24924 KB Output is correct
2 Correct 371 ms 179560 KB Output is correct
3 Correct 256 ms 188240 KB Output is correct
4 Correct 368 ms 195152 KB Output is correct
5 Correct 312 ms 187892 KB Output is correct
6 Correct 246 ms 187476 KB Output is correct
7 Correct 243 ms 188240 KB Output is correct
8 Correct 209 ms 188468 KB Output is correct
9 Correct 474 ms 198648 KB Output is correct
10 Correct 287 ms 198228 KB Output is correct
11 Incorrect 377 ms 187624 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 24924 KB Output is correct
2 Correct 371 ms 179560 KB Output is correct
3 Correct 256 ms 188240 KB Output is correct
4 Correct 368 ms 195152 KB Output is correct
5 Correct 312 ms 187892 KB Output is correct
6 Correct 246 ms 187476 KB Output is correct
7 Correct 243 ms 188240 KB Output is correct
8 Correct 209 ms 188468 KB Output is correct
9 Correct 474 ms 198648 KB Output is correct
10 Correct 287 ms 198228 KB Output is correct
11 Incorrect 377 ms 187624 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 5 ms 24920 KB Output is correct
2 Correct 495 ms 187828 KB Output is correct
3 Correct 617 ms 184348 KB Output is correct
4 Correct 439 ms 185036 KB Output is correct
5 Correct 383 ms 176468 KB Output is correct
6 Correct 270 ms 176464 KB Output is correct
7 Correct 257 ms 176688 KB Output is correct
8 Correct 219 ms 176828 KB Output is correct
9 Correct 478 ms 184600 KB Output is correct
10 Correct 622 ms 185940 KB Output is correct
11 Correct 396 ms 176720 KB Output is correct
12 Correct 421 ms 176660 KB Output is correct
13 Correct 327 ms 176980 KB Output is correct
14 Correct 373 ms 178000 KB Output is correct
15 Correct 5 ms 24924 KB Output is correct
16 Correct 5 ms 24940 KB Output is correct
17 Correct 5 ms 24924 KB Output is correct
18 Correct 6 ms 24924 KB Output is correct
19 Correct 5 ms 24888 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Incorrect 503 ms 186388 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 24920 KB Output is correct
2 Correct 5 ms 24924 KB Output is correct
3 Correct 5 ms 24924 KB Output is correct
4 Incorrect 6 ms 27004 KB Output isn't correct
5 Halted 0 ms 0 KB -