Submission #310064

#	Time	Username	Problem	Language	Result	Execution time	Memory
310064		soroush	File Paths (BOI15_fil)	C++14	100 / 100	305 ms	62196 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 dist[maxn];
vector < int > adj[maxn] , pval;
int cnt[maxn];
int cont[maxn];

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

void dfs(int v = 0){
    if(v <= n){
        pval.pb(dist[v]);
        dfs2(v , s - dist[v]);
        for(auto u : adj[v])
            dfs(u);
        dfs2(v , s - dist[v] ,  1);
        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;
    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[v - n] = 1;
            return;
        }
        if(rmn%(rmn/ i) == 0 and cont[rmn / i]){
            ans[v - n] = 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 >> 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: 33 / 33
• Subtask 2: 33 / 33
• Subtask 3: 34 / 34