Submission #792074

# Submission time Handle Problem Language Result Execution time Memory
792074 2023-07-24T14:47:36 Z quanlt206 Sprinkler (JOI22_sprinkler) C++14
0 / 100
10 ms 10068 KB
#include<bits/stdc++.h>
#define X first
#define Y second
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, b, a) for (int i = (b); i >= (a); i--)
#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define MASK(x) (1LL << (x))
#define all(x) begin(x), end(x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
typedef pair<ll, int> pli;
typedef pair<ll, pii> plii;

template<class A, class B>
    bool maximize(A& x, B y) {
        if (x < y) return x = y, true; else return false;
    }
template<class A, class B>
    bool minimize(A& x, B y) {
        if (x > y) return x = y, true; else return false;
    }
/* END OF TEMPLATE */

const int N = 2e5 + 7;

int n, L, P[N];

ll res[N][50], h[N], res2[N][50];

vector<int> v[N];

void dfs(int x, int par) {
    P[x] = par;
    for (auto y : v[x])
        if (y != par) dfs(y, x);
}

void firstQuery() {
    int x, d, w;
    cin>>x>>d>>w;
    FOR(j, 0, d) res2[x][j] = res2[x][j] * w % L;
    int tmp = 1;
    x = P[x];
    while (x != -1 && tmp <= d) {
        res[x][tmp] = res[x][tmp] * w % L;
        tmp++;
        x = P[x];
    }
}

void secondQuery() {
    int x;
    cin>>x;
    ll ans = h[x];
    int tmp = 1;
    int last_x = x;
    ans = ans * res2[x][0] % L;
    FOR(i, 1, 40) ans = ans * res[x][i] % L;
    x = P[x];
//    cout<<x<<" "<<ans<<"\n";
    while (x != -1 && tmp <= 40) {
        FOR(j, tmp, 40) ans = ans * res2[x][j] % L;
//        cout<<x<<" "<<ans<<"\n";
//        ans = ans * res[x][0] % L;
        if (tmp < 40) {
            for (auto y : v[x])
                if (y != last_x && y != P[x])
                    FOR(j, 0, 40)
                        if (tmp + j <= 40) ans = ans * res[y][j] % L; else break;
        }
//        cout<<x<<" "<<ans<<"\n";
//        break;
        last_x = x;
        x = P[x];
        tmp++;
    }
    cout<<ans<<"\n";
}

int main() {
    #ifndef ONLINE_JUDGE
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif // ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>L;
    REP(i, 1, n) {
        int x, y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    FOR(i, 1, n)
        FOR(j, 0, 40) res[i][j] = res2[i][j] = 1;
    FOR(i, 1, n) cin>>h[i];
    dfs(1, -1);
    int Q;
    cin>>Q;
    while (Q--) {
        int type;
        cin>>type;
        if (type == 1) firstQuery(); else secondQuery();
    }
    return 0;
}

Compilation message

sprinkler.cpp: In function 'void secondQuery()':
sprinkler.cpp:75:20: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   75 |                 if (y != last_x && y != P[x])
      |                    ^
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:90:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     freopen("test.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:91:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     freopen("test.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 10068 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 10068 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 10068 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 10068 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 10068 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 10068 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -