oj.uz

Submission #310063

# Submission time Handle Problem Language Result Execution time Memory
310063 2020-10-05T12:36:42 Z soroush File Paths (BOI15_fil) C++14
33 / 100
 57 ms 54016 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 - n] = 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
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 52480 KB Output is correct
2 Correct 36 ms 52600 KB Output is correct
3 Correct 37 ms 52480 KB Output is correct
4 Correct 36 ms 52480 KB Output is correct
5 Correct 56 ms 54008 KB Output is correct
6 Correct 57 ms 54016 KB Output is correct
7 Correct 44 ms 51704 KB Output is correct
8 Correct 44 ms 51712 KB Output is correct
9 Correct 37 ms 51968 KB Output is correct
10 Correct 35 ms 51584 KB Output is correct
11 Correct 35 ms 47608 KB Output is correct
12 Correct 44 ms 50304 KB Output is correct

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 -