Submission #310057

#	Time	Username	Problem	Language	Result	Execution time	Memory
310057		soroush	File Paths (BOI15_fil)	C++14	0 / 100	46 ms	59896 KiB

fil

/*
#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 val[maxn];
int num[maxn];
int dist[maxn];
int cnt[maxn];
int cont[maxn];
vector < int > adj[maxn] , par;

void dfs2(int v,int val, bool f = 0){
    if(dist[v] + val <= 1e6)cont[dist[v] + val] += ((f) ? -1 : 1);
    for(auto u : adj[v])
        dfs2(u ,val ,f);
}

void dfs(int v = 0){
    if(!num[v]){
        par.pb(dist[v]);
        dfs2(v , s - dist[v]);
        for(int u : adj[v])
            dfs(u);
        par.pop_back();
        dfs2(v , s - dist[v] ,  1);
        return;
    }
    for(auto x : par){
        int bz = k + x - s - dist[v];
        if(bz >= 0 and cnt[bz]){
            ans[num[v]] = 1;
            return;
        }
    }
    int rmn = k - dist[v];
    if(rmn <= 0)
        return;
    for(int i = 1 ; i * i <= rmn ; i ++){
        if(rmn%i == 0 and cont[i] ){
            ans[num[v]] = 1;
            return;
        }
        if(rmn%i == 0 and cont[rmn / i]){
            ans[num[v]] = 1;
            return;
        }
    }
}

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 >> val[i];
        val[i] ++ ;
        dist[i] = val[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 >> val[i];
        num[i] = i - n;
        dist[i] = dist[p] + val[i];
        if(dist[i] == k) ans[num[i]] = 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
• Subtask 2: 0 / 33
• Subtask 3: 0 / 34