oj.uz

Submission #785514

# Submission time Handle Problem Language Result Execution time Memory
785514 2023-07-17T09:50:19 Z kebine Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 30272 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;
    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(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;
    //     }
    // }

    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
3.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 11 ms 5108 KB Output is correct
7 Correct 11 ms 5116 KB Output is correct
8 Correct 15 ms 5128 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 2 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 2 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 Correct 2 ms 4948 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 2 ms 4948 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 3 ms 4948 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Correct 3 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 283 ms 30112 KB Output is correct
3 Correct 1222 ms 26996 KB Output is correct
4 Correct 718 ms 27412 KB Output is correct
5 Correct 751 ms 28496 KB Output is correct
6 Correct 773 ms 28516 KB Output is correct
7 Correct 780 ms 28840 KB Output is correct
8 Correct 753 ms 29036 KB Output is correct
9 Correct 289 ms 28964 KB Output is correct
10 Correct 1301 ms 25868 KB Output is correct
11 Correct 295 ms 30064 KB Output is correct
12 Correct 1227 ms 26848 KB Output is correct
13 Execution timed out 4053 ms 30272 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 283 ms 30112 KB Output is correct
3 Correct 1222 ms 26996 KB Output is correct
4 Correct 718 ms 27412 KB Output is correct
5 Correct 751 ms 28496 KB Output is correct
6 Correct 773 ms 28516 KB Output is correct
7 Correct 780 ms 28840 KB Output is correct
8 Correct 753 ms 29036 KB Output is correct
9 Correct 289 ms 28964 KB Output is correct
10 Correct 1301 ms 25868 KB Output is correct
11 Correct 295 ms 30064 KB Output is correct
12 Correct 1227 ms 26848 KB Output is correct
13 Execution timed out 4053 ms 30272 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 Correct 429 ms 26344 KB Output is correct
3 Correct 2542 ms 25700 KB Output is correct
4 Correct 1240 ms 25980 KB Output is correct
5 Correct 3867 ms 26952 KB Output is correct
6 Execution timed out 4043 ms 27220 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 467 ms 29008 KB Output is correct
3 Correct 2619 ms 26008 KB Output is correct
4 Correct 1113 ms 27388 KB Output is correct
5 Correct 3560 ms 28536 KB Output is correct
6 Execution timed out 4070 ms 27328 KB Time limit exceeded
7 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 11 ms 5108 KB Output is correct
7 Correct 11 ms 5116 KB Output is correct
8 Correct 15 ms 5128 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 2 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 2 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 Correct 2 ms 4948 KB Output is correct
22 Correct 2 ms 4948 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 2 ms 4948 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 3 ms 4948 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Correct 3 ms 4948 KB Output is correct
29 Correct 3 ms 4948 KB Output is correct
30 Correct 283 ms 30112 KB Output is correct
31 Correct 1222 ms 26996 KB Output is correct
32 Correct 718 ms 27412 KB Output is correct
33 Correct 751 ms 28496 KB Output is correct
34 Correct 773 ms 28516 KB Output is correct
35 Correct 780 ms 28840 KB Output is correct
36 Correct 753 ms 29036 KB Output is correct
37 Correct 289 ms 28964 KB Output is correct
38 Correct 1301 ms 25868 KB Output is correct
39 Correct 295 ms 30064 KB Output is correct
40 Correct 1227 ms 26848 KB Output is correct
41 Execution timed out 4053 ms 30272 KB Time limit exceeded
42 Halted 0 ms 0 KB -