oj.uz

Submission #785525

# Submission time Handle Problem Language Result Execution time Memory
785525 2023-07-17T09:59:39 Z devariaota Sprinkler (JOI22_sprinkler) C++17
0 / 100
 4000 ms 30168 KB 
#include <bits/stdc++.h>
using namespace std;

# define int long long
# define fir first
# define sec second
# define pb push_back
# define endl "\n"

const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;


int F[cnst];
int inv[cnst];

int A(int a, int b, int mod) {return ((a%mod)+(b%mod)%mod);}
int S(int a, int b, int mod) {return ((a%mod)-(b%mod)+mod)%mod;}
int M(int a, int b, int mod) {return ((a%mod)*(b%mod)%mod);}

int E(int b, int p, int mod) {
    if(!p) return 1;
    return (p%2 ? M(E(M(b, b, mod), p/2, mod), b, mod) : E(M(b, b, mod), p/2, mod));
}

int C(int n, int r, int mod) {return M(M(F[n], inv[n-r], mod), inv[r], mod);}

void prefac(int maxn, int mod) {
    F[0] = 1;
    for(int i = 1; i<=maxn; i++) F[i] = M(F[i-1], i, mod);
    inv[maxn] = E(F[maxn], mod-2, mod);
    for(int i = maxn-1; i>=0; i--) inv[i] = M(inv[i+1], i+1, mod);
}

int gcd(int a, int b) {return b ? gcd(b, a%b): a;}
int lcm(int a, int b) {return a/gcd(a, b)*b;}

int par[cnst];
int val[cnst];
vector<int> vec[cnst];

void dfs(int x) {
    for(auto v: vec[x]) {
        if(v == par[x]) continue;
        par[v] = x;
        dfs(v);
    }
}

void solve() {
    int n, l; cin >> n >> l;

    for(int i = 1; i<n; i++) {
        int a, b; cin >> a >> b;
        vec[a].pb(b);
        vec[b].pb(a);
    } 

    for(int i = 1; i<=n; i++) cin >> val[i];

    int q; cin >> q;
    
    bool yes = 1;
    bool yes2 = 1;
    tuple<int, int, int, int> quer[q+5];

    for(int i = 1; i<=q; i++) {
        int id; cin >> id;
        int a, b = -1, c = -1;
        if(id == 1) cin >> a >> b >> c;
        else cin >> a;

        quer[i] = {id, a, b, c};
        if(id == 1 && b > 1) yes = 0; 
        if(id == 1 && c != 0) yes2 = 0;
    }

    // if(yes) {
    //     for(int i = 1; i<=q; i++) {
    //         auto[a, x, d, k] = quer[i];
    //         if(a == 1) {
    //             val[x] = M(val[x], k, l);
    //             if(d == 0) continue;
    //             for(auto v: vec[x]) val[v] = M(val[v], k, l);
    //         }
    //         else cout << val[x] << endl;
    //     }
    // }

    if(yes2) {
        int mx[n+5];
        memset(mx, 0, sizeof(mx));
        for(int i = 1; i<=q; i++) {
            auto[a, x, d, k] = quer[i];
            if(a == 2) {
                cout << val[x] << endl;
                continue;
            }
            else if(mx[x] >= d) continue;

            queue<pair<int, int>> q;
            // bool vis[n+5];
            // memset(vis, 0, sizeof(vis));
            q.push({x, d}); mx[x] = d;

            while(!q.empty()) {
                auto[a, dis] = q.front(); q.pop();

                val[a] = 0;
                if(dis == 0) continue;

                for(auto v: vec[a]) {
                    if(mx[v] < (dis-1)) {
                        mx[v] = dis-1;
                        q.push({v, dis-1});
                    }
                }
            }
        }
        return;
    }

    for(int i = 1; i<=q; i++) {
        auto[a, x, d, k] = quer[i];
        if(a == 2) {
            cout << val[x] << endl;
            continue;
        }

        queue<pair<int, int>> q;
        bool vis[n+5];
        memset(vis, 0, sizeof(vis));
        q.push({x, 0}); vis[x] = 1;

        while(!q.empty()) {
            auto[a, dis] = q.front(); q.pop();

            val[a] = M(val[a], k, l);
            if(dis == d) continue;

            for(auto v: vec[a]) {
                if(!vis[v]) {
                    vis[v] = 1;
                    q.push({v, dis+1});
                }
            }
        }
    }


}

signed main() {
    ios_base::sync_with_stdio(false);
    int t = 1;
    if(mutipletestcase) cin >> t; 
    while(t--) solve();
}

Compilation message

sprinkler.cpp: In function 'void solve()':
sprinkler.cpp:64:10: warning: variable 'yes' set but not used [-Wunused-but-set-variable]
   64 |     bool yes = 1;
      |          ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Correct 10 ms 5108 KB Output is correct
7 Correct 15 ms 5104 KB Output is correct
8 Correct 16 ms 5124 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4952 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 3 ms 5096 KB Output is correct
21 Incorrect 3 ms 4948 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 358 ms 30168 KB Output is correct
3 Correct 1242 ms 27096 KB Output is correct
4 Correct 748 ms 27420 KB Output is correct
5 Correct 875 ms 28468 KB Output is correct
6 Correct 853 ms 28592 KB Output is correct
7 Correct 798 ms 28980 KB Output is correct
8 Correct 792 ms 29184 KB Output is correct
9 Correct 321 ms 28964 KB Output is correct
10 Correct 1423 ms 25928 KB Output is correct
11 Correct 309 ms 30028 KB Output is correct
12 Correct 1346 ms 26960 KB Output is correct
13 Execution timed out 4053 ms 30016 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 358 ms 30168 KB Output is correct
3 Correct 1242 ms 27096 KB Output is correct
4 Correct 748 ms 27420 KB Output is correct
5 Correct 875 ms 28468 KB Output is correct
6 Correct 853 ms 28592 KB Output is correct
7 Correct 798 ms 28980 KB Output is correct
8 Correct 792 ms 29184 KB Output is correct
9 Correct 321 ms 28964 KB Output is correct
10 Correct 1423 ms 25928 KB Output is correct
11 Correct 309 ms 30028 KB Output is correct
12 Correct 1346 ms 26960 KB Output is correct
13 Execution timed out 4053 ms 30016 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 249 ms 27856 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 522 ms 29164 KB Output is correct
3 Correct 3072 ms 26056 KB Output is correct
4 Correct 1637 ms 27488 KB Output is correct
5 Execution timed out 4073 ms 28284 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Correct 10 ms 5108 KB Output is correct
7 Correct 15 ms 5104 KB Output is correct
8 Correct 16 ms 5124 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4952 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 3 ms 5096 KB Output is correct
21 Incorrect 3 ms 4948 KB Output isn't correct
22 Halted 0 ms 0 KB -