oj.uz

Submission #785537

# Submission time Handle Problem Language Result Execution time Memory
785537 2023-07-17T10:05:52 Z christinelynn Sprinkler (JOI22_sprinkler) C++17
15 / 100
 4000 ms 33364 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], val2[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];
    for(int i = 1; i<=n; i++) val2[i] = 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, -1, sizeof(mx));
        for(int i = 1; i<=q; i++) {
            auto[a, x, d, k] = quer[i];
            if(a == 2) {
                cout << val2[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();

                val2[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});
                    }
                }
            }

            // for(int i = 1; i<=n; i++) cerr << val2[i] << " "; cerr << endl;
        }
        return;
        cerr << endl;
    }

    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});
                }
            }
        }
        // for(int i = 1; i<=n; i++) cerr << val[i] << " "; cerr << endl;
    }
}

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:65:10: warning: variable 'yes' set but not used [-Wunused-but-set-variable]
   65 |     bool yes = 1;
      |          ^~~

Subtask #1
3.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 10 ms 5124 KB Output is correct
7 Correct 11 ms 5076 KB Output is correct
8 Correct 16 ms 5140 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 4 ms 4948 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 4 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 4 ms 4948 KB Output is correct
25 Correct 3 ms 5056 KB Output is correct
26 Correct 2 ms 4948 KB Output is correct
27 Correct 2 ms 4948 KB Output is correct
28 Correct 4 ms 4948 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 316 ms 31808 KB Output is correct
3 Correct 1357 ms 28608 KB Output is correct
4 Correct 794 ms 29060 KB Output is correct
5 Correct 822 ms 30232 KB Output is correct
6 Correct 756 ms 30240 KB Output is correct
7 Correct 744 ms 30568 KB Output is correct
8 Correct 732 ms 30792 KB Output is correct
9 Correct 308 ms 30544 KB Output is correct
10 Correct 1287 ms 27500 KB Output is correct
11 Correct 324 ms 31668 KB Output is correct
12 Correct 1221 ms 28512 KB Output is correct
13 Execution timed out 4062 ms 31868 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 316 ms 31808 KB Output is correct
3 Correct 1357 ms 28608 KB Output is correct
4 Correct 794 ms 29060 KB Output is correct
5 Correct 822 ms 30232 KB Output is correct
6 Correct 756 ms 30240 KB Output is correct
7 Correct 744 ms 30568 KB Output is correct
8 Correct 732 ms 30792 KB Output is correct
9 Correct 308 ms 30544 KB Output is correct
10 Correct 1287 ms 27500 KB Output is correct
11 Correct 324 ms 31668 KB Output is correct
12 Correct 1221 ms 28512 KB Output is correct
13 Execution timed out 4062 ms 31868 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 270 ms 29320 KB Output is correct
3 Correct 291 ms 28480 KB Output is correct
4 Correct 247 ms 28832 KB Output is correct
5 Correct 242 ms 29920 KB Output is correct
6 Correct 333 ms 30424 KB Output is correct
7 Correct 361 ms 30564 KB Output is correct
8 Correct 208 ms 33364 KB Output is correct
9 Correct 226 ms 29360 KB Output is correct
10 Correct 322 ms 28496 KB Output is correct
11 Correct 287 ms 30180 KB Output is correct
12 Correct 274 ms 29584 KB Output is correct
13 Correct 233 ms 30504 KB Output is correct
14 Correct 248 ms 31160 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 3 ms 4996 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 472 ms 30712 KB Output is correct
3 Correct 2807 ms 27744 KB Output is correct
4 Correct 1264 ms 29200 KB Output is correct
5 Execution timed out 4072 ms 30360 KB Time limit exceeded
6 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 10 ms 5124 KB Output is correct
7 Correct 11 ms 5076 KB Output is correct
8 Correct 16 ms 5140 KB Output is correct
9 Correct 4 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 4 ms 4948 KB Output is correct
13 Correct 4 ms 4948 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 4 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 4 ms 4948 KB Output is correct
25 Correct 3 ms 5056 KB Output is correct
26 Correct 2 ms 4948 KB Output is correct
27 Correct 2 ms 4948 KB Output is correct
28 Correct 4 ms 4948 KB Output is correct
29 Correct 3 ms 4948 KB Output is correct
30 Correct 316 ms 31808 KB Output is correct
31 Correct 1357 ms 28608 KB Output is correct
32 Correct 794 ms 29060 KB Output is correct
33 Correct 822 ms 30232 KB Output is correct
34 Correct 756 ms 30240 KB Output is correct
35 Correct 744 ms 30568 KB Output is correct
36 Correct 732 ms 30792 KB Output is correct
37 Correct 308 ms 30544 KB Output is correct
38 Correct 1287 ms 27500 KB Output is correct
39 Correct 324 ms 31668 KB Output is correct
40 Correct 1221 ms 28512 KB Output is correct
41 Execution timed out 4062 ms 31868 KB Time limit exceeded
42 Halted 0 ms 0 KB -