oj.uz

Submission #521304

# Submission time Handle Problem Language Result Execution time Memory
521304 2022-02-01T14:58:30 Z radal File Paths (BOI15_fil) C++14
100 / 100
 273 ms 5756 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
//#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
const long long int N = 6e3+20,mod = 998244353,inf = 1e9+10,maxm = 2e6+10,sq = 1001;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}

inline int poww(int a,int k){
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    }
    return z;
}
int h[N],n,m,k,s,par[N],L[N];;
int cnt[maxm];
bool b[maxm];
vector<pll> adj[N];
bool ok[N];
void dfs2(int u,int v,int t){
    if (u <= n) cnt[h[u]-h[v]+s] += t;
    for (pll w : adj[u]) dfs2(w.X,v,t);
}
void dfs(int v){
    if (v <= n){
        b[h[v]] = 1;
        int w = v;
        while (w > -1){
            cnt[h[v]-h[w]+s]++;
            w = par[w];
        }
        dfs2(v,v,1);
    }
    else{
        if(k == h[v]) ok[v] = 1;
        rep(i,1,sq+1){
            if (ok[v]) break;
            if ((k-h[v])%i) continue;
            if (cnt[(k-h[v])/i] || cnt[i]){
                ok[v] = 1;
                break;
            }
        }
        return;
    }
    for(pll u : adj[v]){
        dfs(u.X);
    }
    dfs2(v,v,-1);
    int w = v;
    while (w > -1){
        cnt[h[v]-h[w]+s]--;
        w = par[w];
    }
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    cin >> n >> m >> k >> s;
    s++;
    rep(i,1,n+1){
        int p,l;
        cin >> p >> l;
        par[i] = p;
        h[i] = h[p]+l+1;
        adj[p].pb({i,l+1});
    }
    rep(i,1,m+1){
        int p,l;
        cin >> p >> l;
        par[i+n] = p;
        h[i+n] = h[p]+l+1;
        L[i] = l;
        adj[p].pb({i+n,l+1});
    }
    par[0] = -1;
    dfs(0);
    rep(i,1,m+1){
        if (k  == h[i+n]){
            cout << "YES" << endl;
            continue;
        }
        int v = par[i+n];
        while (v >= 0){
            int t = s+h[i+n]-h[v];
            if (k >= t && b[k-t]){
                ok[i+n] = 1;
                break;
            }
            v = par[v];
        }
        if (ok[i+n]){
            cout << "YES" << endl;
            continue;
        }
        cout << "NO" << endl;
    }
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 472 KB Output is correct
3 Correct 3 ms 928 KB Output is correct
4 Correct 5 ms 964 KB Output is correct
5 Correct 5 ms 4812 KB Output is correct
6 Correct 5 ms 3660 KB Output is correct
7 Correct 9 ms 5196 KB Output is correct
8 Correct 5 ms 4460 KB Output is correct
9 Correct 4 ms 4428 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 5 ms 900 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5476 KB Output is correct
2 Correct 19 ms 5472 KB Output is correct
3 Correct 19 ms 5452 KB Output is correct
4 Correct 21 ms 5388 KB Output is correct
5 Correct 215 ms 5752 KB Output is correct
6 Correct 237 ms 5740 KB Output is correct
7 Correct 137 ms 5608 KB Output is correct
8 Correct 121 ms 5572 KB Output is correct
9 Correct 20 ms 5408 KB Output is correct
10 Correct 19 ms 5340 KB Output is correct
11 Correct 19 ms 784 KB Output is correct
12 Correct 242 ms 2444 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 472 KB Output is correct
3 Correct 3 ms 928 KB Output is correct
4 Correct 5 ms 964 KB Output is correct
5 Correct 5 ms 4812 KB Output is correct
6 Correct 5 ms 3660 KB Output is correct
7 Correct 9 ms 5196 KB Output is correct
8 Correct 5 ms 4460 KB Output is correct
9 Correct 4 ms 4428 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 5 ms 900 KB Output is correct
13 Correct 18 ms 5476 KB Output is correct
14 Correct 19 ms 5472 KB Output is correct
15 Correct 19 ms 5452 KB Output is correct
16 Correct 21 ms 5388 KB Output is correct
17 Correct 215 ms 5752 KB Output is correct
18 Correct 237 ms 5740 KB Output is correct
19 Correct 137 ms 5608 KB Output is correct
20 Correct 121 ms 5572 KB Output is correct
21 Correct 20 ms 5408 KB Output is correct
22 Correct 19 ms 5340 KB Output is correct
23 Correct 19 ms 784 KB Output is correct
24 Correct 242 ms 2444 KB Output is correct
25 Correct 14 ms 5412 KB Output is correct
26 Correct 14 ms 5320 KB Output is correct
27 Correct 15 ms 5340 KB Output is correct
28 Correct 16 ms 5456 KB Output is correct
29 Correct 273 ms 5756 KB Output is correct
30 Correct 220 ms 5724 KB Output is correct
31 Correct 121 ms 5572 KB Output is correct
32 Correct 151 ms 5520 KB Output is correct
33 Correct 16 ms 5424 KB Output is correct
34 Correct 15 ms 5356 KB Output is correct
35 Correct 15 ms 668 KB Output is correct
36 Correct 265 ms 1680 KB Output is correct