Submission #877046

#	Time	Username	Problem	Language	Result	Execution time	Memory
877046		Ice_man	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	835 ms	113336 KiB

sprinkler

#include <iostream>
#include <chrono>
#include <vector>
#include <cstring>

#define maxn 200005
#define maxlog 20
#define maxd 45
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "fast-math" , "unroll-loops")
#pragma GCC target(avx2)

using namespace std;

std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}

struct query
{
    long long node , distance , weight;
    query(){};
    query(long long node2 , long long distance2 , long long weight2)
    {
        node = node2;
        distance = distance2;
        weight = weight2;
    }
};

long long n;
long long mod;
vector <long long> v[maxn];
vector < query > queries;
long long q;
long long num[maxn];

void read()
{
    cin >> n >> mod;

    long long from , to;
    for(long long i = 1; i <= (n - 1); i++)
    {
        cin >> from >> to;

        v[from].pb(to);
        v[to].pb(from);
    }

    for(long long i = 1; i <= n; i++) cin >> num[i];

    cin >> q;

    queries.resize(q + 1);
    long long t;

    for(long long i = 1; i <= q; i++)
    {
        cin >> t;
        if(t == 1) cin >> queries[i].node >> queries[i].distance >> queries[i].weight;
        else
        {
            cin >> queries[i].node;
            queries[i].distance = -1;
        }
    }
}

long long depth[maxn];
long long parent[maxn];

void dfs(long long node , long long cur_parent)
{

    for(long long nb : v[node]) if(nb != cur_parent)
    {
        parent[nb] = node;
        depth[nb] = depth[node] + 1;

        dfs(nb , node);

    }

}

long long multiply[maxn][maxd];

void rec(long long node , long long distance , long long weight)
{

    ///cout << node << " " << distance << " " << weight << endl;

    if(node == 0) return;
    if(distance == -1) return;

    rec(parent[node] , distance - 1 , weight);

    if(node == 1) for(long long i = 0; i <= distance; i++) multiply[node][i] = (multiply[node][i] * weight) % mod;
    else
    {
        multiply[node][distance] *= weight;
        multiply[node][distance] %= mod;

        if(distance)
        {
            multiply[node][distance - 1] *= weight;
            multiply[node][distance - 1] %= mod;
        }

    }

}

long long find_number(long long node , long long cur_depth)
{
    if(node == 1) return (multiply[node][cur_depth] % mod);
    if(cur_depth >= 1) return (multiply[node][cur_depth] % mod);

    return find_number(parent[node] , cur_depth + 1) % mod;

}


void solve()
{
    ///memset(multiply , 1 , sizeof(multiply));

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


    for(long long i = 1; i <= q; i++)
    {
        if(queries[i].distance == -1)
        {

            long long ans = num[queries[i].node];
            long long node = queries[i].node;

            ///cout << ". " << ans << endl;

            for(long long j = 0; j <= 40; j++)
            {
                ans *= multiply[node][j];
                ans %= mod;

                ///cout << "= " << node << " " << multiply[node][j] << " " << j << endl;

                /**if(parent[node] == 0) break;
                node = parent[node];*/

                if(parent[node] != 0) node = parent[node];
                else break;

            }

            /**ans *= find_number(queries[i].node , 0) << endl;
            ans %= mod;*/

            cout << ans << endl;

        }
        else rec(queries[i].node , queries[i].distance , queries[i].weight);
    }


}

int main()
{

#ifdef ONLINE_JUDGE
    freopen("taxi.in", "r", stdin);
    freopen("taxi.out", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    startT = std::chrono::high_resolution_clock::now();

    read();
    dfs(1 , 0);
    ///cout << "--------------" << endl;

    solve();

    return 0;
}

Compilation message (stderr)

sprinkler.cpp:18:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
   18 | #pragma GCC target(avx2)
      |                    ^~~~

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 29 / 29
• Subtask 4: 12 / 12
• Subtask 5: 30 / 30
• Subtask 6: 17 / 17