oj.uz

Submission #310062

# Submission time Handle Problem Language Result Execution time Memory
310062 2020-10-05T12:36:20 Z soroush File Paths (BOI15_fil) C++14
0 / 100
 36 ms 52472 KB 
/*
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
//*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int  ,int > pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn  = 2e6+1000;
const ll mod =1e9+7;
const ld PI = acos((ld)-1);

#define int ll
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ms(x , y) memset(x , y , sizeof x);
#define file_init freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n , m , k;
int ans[maxn];
int s;
int dist[maxn];
vector < int > adj[maxn] , pval;
int cnt[maxn];

void dfs(int v = 0){
    if(v <= n){
        pval.pb(dist[v]);
        for(auto u : adj[v])
            dfs(u);
        pval.pop_back();
        return;
    }
    for(auto x : pval)
        if(k - (dist[v] - x) - s >= 0 and cnt[k - (dist[v] - x) - s ])
            ans[v] = 1;
}

int32_t main(){
    migmig
    cin >> n >> m >> k;
    cin >> s;
    s++;
    dist[0] = 1;
    for(int i = 1 ; i <= n ; i ++){
        int p;
        cin >> p >> dist[i];
        dist[i] ++ ;
        dist[i] += dist[p];
        adj[p].pb(i);
    }
    for(int i = 0 ; i <= n ; i ++) cnt[dist[i]] ++;
    for(int i = n+1; i <= n + m ; i ++){
        int p;
        cin >> p >> dist[i];
        dist[i] += dist[p];
        if(dist[i] == k) ans[i - n] = 1;
        else adj[p].pb(i);
    }
    dfs();
    for(int i = 1 ; i <= m ; i ++)
        cout << ((ans[i])?"YES" : "NO") << endl;
    return(0);
}

Subtask #1
0 / 33.0

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

Subtask #2
0 / 33.0

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

Subtask #3
0 / 34.0

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