oj.uz

Submission #878459

# Submission time Handle Problem Language Result Execution time Memory
878459 2023-11-24T11:57:26 Z borisAngelov Sprinkler (JOI22_sprinkler) C++17
21 / 100
 2587 ms 104812 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;
const int maxDepth = 40;

int n, q;
long long mod;

vector<int> g[maxn];

long long height[maxn];

long long lazy[maxn][maxDepth + 5];

int parent[maxn];

void dfs(int node, int par)
{
    parent[node] = par;

    for (int i = 0; i < g[node].size(); ++i)
    {
        if (g[node][i] != par)
        {
            dfs(g[node][i], node);
        }
    }
}

void update(int node, int dist, long long mult)
{
    while (node != -1 && dist >= 0)
    {
        for (int i = dist; i >= 0; --i)
        {
            lazy[node][i] *= mult;
            lazy[node][i] %= mod;
        }

        --dist;
        node = parent[node];
    }
}

long long query(int node)
{
    int dist = 0;
    long long ans = height[node];

    while (node != -1 && dist <= 40)
    {
        ans = (ans * lazy[node][dist]) % mod;
        node = parent[node];
        ++dist;
    }

    return ans;
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> mod;

    for (int i = 1; i <= n - 1; ++i)
    {
        int x, y;
        cin >> x >> y;

        g[x].push_back(y);
        g[y].push_back(x);
    }

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

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= maxDepth; ++j)
        {
            lazy[i][j] = 1;
        }
    }

    dfs(1, -1);

    cin >> q;

    for (int i = 1; i <= q; ++i)
    {
        int type;
        cin >> type;

        if (type == 1)
        {
            int node, dist, mult;
            cin >> node >> dist >> mult;
            update(node, dist, mult);
        }
        else
        {
            int node;
            cin >> node;
            cout << query(node) << "\n";
        }
    }

    return 0;
}

Compilation message

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

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9816 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 9816 KB Output is correct
2 Correct 382 ms 95868 KB Output is correct
3 Correct 257 ms 96848 KB Output is correct
4 Correct 378 ms 101984 KB Output is correct
5 Correct 307 ms 96336 KB Output is correct
6 Correct 227 ms 95864 KB Output is correct
7 Correct 222 ms 96592 KB Output is correct
8 Correct 188 ms 96968 KB Output is correct
9 Correct 473 ms 104812 KB Output is correct
10 Correct 269 ms 104532 KB Output is correct
11 Correct 354 ms 95856 KB Output is correct
12 Correct 246 ms 96084 KB Output is correct
13 Correct 170 ms 96660 KB Output is correct
14 Correct 181 ms 97308 KB Output is correct
15 Correct 173 ms 96596 KB Output is correct
16 Correct 174 ms 97108 KB Output is correct
17 Correct 186 ms 97476 KB Output is correct
18 Correct 2 ms 10076 KB Output is correct
19 Correct 2 ms 10076 KB Output is correct
20 Correct 2 ms 10076 KB Output is correct
21 Correct 2 ms 10076 KB Output is correct
22 Correct 2 ms 10076 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 382 ms 95868 KB Output is correct
3 Correct 257 ms 96848 KB Output is correct
4 Correct 378 ms 101984 KB Output is correct
5 Correct 307 ms 96336 KB Output is correct
6 Correct 227 ms 95864 KB Output is correct
7 Correct 222 ms 96592 KB Output is correct
8 Correct 188 ms 96968 KB Output is correct
9 Correct 473 ms 104812 KB Output is correct
10 Correct 269 ms 104532 KB Output is correct
11 Correct 354 ms 95856 KB Output is correct
12 Correct 246 ms 96084 KB Output is correct
13 Correct 170 ms 96660 KB Output is correct
14 Correct 181 ms 97308 KB Output is correct
15 Correct 173 ms 96596 KB Output is correct
16 Correct 174 ms 97108 KB Output is correct
17 Correct 186 ms 97476 KB Output is correct
18 Correct 2 ms 10076 KB Output is correct
19 Correct 2 ms 10076 KB Output is correct
20 Correct 2 ms 10076 KB Output is correct
21 Correct 2 ms 10076 KB Output is correct
22 Correct 2 ms 10076 KB Output is correct
23 Correct 2 ms 9820 KB Output is correct
24 Incorrect 369 ms 96076 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 733 ms 102144 KB Output is correct
3 Correct 2549 ms 100352 KB Output is correct
4 Correct 860 ms 100444 KB Output is correct
5 Correct 703 ms 93212 KB Output is correct
6 Correct 503 ms 93340 KB Output is correct
7 Correct 417 ms 93368 KB Output is correct
8 Correct 233 ms 94092 KB Output is correct
9 Correct 716 ms 99188 KB Output is correct
10 Correct 2587 ms 102008 KB Output is correct
11 Correct 553 ms 92752 KB Output is correct
12 Correct 1914 ms 93912 KB Output is correct
13 Correct 1543 ms 94820 KB Output is correct
14 Correct 1552 ms 95548 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 3 ms 10068 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 10056 KB Output is correct
19 Correct 3 ms 9904 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9820 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 9816 KB Output isn't correct
2 Halted 0 ms 0 KB -