oj.uz

Submission #785522

# Submission time Handle Problem Language Result Execution time Memory
785522 2023-07-17T09:57:42 Z andecaandeci Sprinkler (JOI22_sprinkler) C++17
0 / 100
 4000 ms 30260 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 max[n+5];
        memset(max, 0, sizeof(max));
        for(int i = 1; i<=q; i++) {
            auto[a, x, d, k] = quer[i];
            if(a == 2) {
                cout << val[x] << endl;
                continue;
            }
            else if(max[x] >= d) continue;

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

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

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

                for(auto v: vec[a]) {
                    if(max[v] < dis) {
                        max[v] = dis;
                        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 3 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 12 ms 5108 KB Output is correct
7 Correct 12 ms 5116 KB Output is correct
8 Correct 16 ms 5132 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 4 ms 5064 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Incorrect 4 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 3 ms 4948 KB Output is correct
2 Correct 309 ms 30160 KB Output is correct
3 Correct 1218 ms 26992 KB Output is correct
4 Correct 761 ms 27440 KB Output is correct
5 Correct 752 ms 28496 KB Output is correct
6 Correct 744 ms 28672 KB Output is correct
7 Correct 754 ms 29036 KB Output is correct
8 Correct 717 ms 29104 KB Output is correct
9 Correct 280 ms 28956 KB Output is correct
10 Correct 1213 ms 25888 KB Output is correct
11 Correct 288 ms 30148 KB Output is correct
12 Correct 1212 ms 26948 KB Output is correct
13 Execution timed out 4059 ms 30260 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 309 ms 30160 KB Output is correct
3 Correct 1218 ms 26992 KB Output is correct
4 Correct 761 ms 27440 KB Output is correct
5 Correct 752 ms 28496 KB Output is correct
6 Correct 744 ms 28672 KB Output is correct
7 Correct 754 ms 29036 KB Output is correct
8 Correct 717 ms 29104 KB Output is correct
9 Correct 280 ms 28956 KB Output is correct
10 Correct 1213 ms 25888 KB Output is correct
11 Correct 288 ms 30148 KB Output is correct
12 Correct 1212 ms 26948 KB Output is correct
13 Execution timed out 4059 ms 30260 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 227 ms 27708 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 460 ms 29068 KB Output is correct
3 Correct 2711 ms 25936 KB Output is correct
4 Correct 1236 ms 27528 KB Output is correct
5 Correct 3620 ms 28476 KB Output is correct
6 Execution timed out 4081 ms 27216 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 12 ms 5108 KB Output is correct
7 Correct 12 ms 5116 KB Output is correct
8 Correct 16 ms 5132 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 4 ms 5064 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Incorrect 4 ms 4948 KB Output isn't correct
22 Halted 0 ms 0 KB -