oj.uz

Submission #681009

# Submission time Handle Problem Language Result Execution time Memory
681009 2023-01-12T08:49:45 Z DwightKSchrute Sprinkler (JOI22_sprinkler) C++17
12 / 100
 719 ms 102568 KB 
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 */
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
typedef vector<pi> vpi;

//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define outfl(x){cout << x << endl;return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map


template<typename T>
void read(vector<T>& v){
    int n=v.size();
    for(int i=0; i<n; i++)
        cin >> v[i];
}
template<typename T>
vector<T>UNQ(vector<T>a){
    vector<T>ans;
    for(T t:a)
        if(ans.empty() || t!=ans.back())
            ans.push_back(t);
    return ans;
}



void solve();
int main(){
    GLHF;
    int t=1;
    //cin >> t;
    while(t--)
        solve();
}
ll n,m;
vvi g;
vl a;
vvl lazy;
vi up,D;
const int MAX_D = 40;
void dfs(int x,int p){
    for(int nbr:g[x])
        if(nbr!=p)
            up[nbr]=x,dfs(nbr,x);
}
ll qur(int x){
    int xx=x;
    for(int d=0; d<=MAX_D && x!=-1; d++){
        if(D[x]>=d)
            return 0;
        x=up[x];
    }
    return a[xx];
}

void upd(ll x,ll d,ll w){
    for(; d>=0 && x!=-1; d--){
        D[x] = max(1ll*D[x],d);
        x=up[x];
    }
}
void solve() {
    cin >> n >> m;
    g.resize(n+1);
    for(int i=0; i<n-1; i++){
        int u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    a.resize(n+1);
    for(int i=1; i<=n; i++)
        cin >> a[i];
    D.resize(n+1,-1e9);

    up.resize(n+1,-1);
    lazy.resize(n+1,vl(MAX_D + 1, 1));
    dfs(1,-1);

    int q;
    cin >> q;
    while(q--){
        int op;
        cin >> op;
        if(op==2){
            int x;
            cin >> x;
            cout << qur(x) << endl;
        }
        else{
            ll x,d,w;
            cin >> x >> d >> w;
            upd(x,d,w);
        }
    }
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 719 ms 102568 KB Output is correct
3 Correct 593 ms 101188 KB Output is correct
4 Correct 579 ms 101052 KB Output is correct
5 Correct 578 ms 93992 KB Output is correct
6 Correct 525 ms 94072 KB Output is correct
7 Correct 493 ms 94172 KB Output is correct
8 Correct 444 ms 94916 KB Output is correct
9 Correct 719 ms 100168 KB Output is correct
10 Correct 527 ms 102496 KB Output is correct
11 Correct 710 ms 93644 KB Output is correct
12 Correct 534 ms 94588 KB Output is correct
13 Correct 449 ms 95376 KB Output is correct
14 Correct 442 ms 96060 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 320 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -