Submission #874639

#	Time	Username	Problem	Language	Result	Execution time	Memory
874639		Iliya_	File Paths (BOI15_fil)	C++17	100 / 100	183 ms	69228 KiB

fil

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl        '\n'
#define F           first
#define S           second
#define all(x)      x.begin(),x.end()
#define pb          push_back
using namespace std;
typedef long long ll; 

#define int long long 
const int N = 2e6+7; 
vector<int> g[N], jad;
int dist[N], mos[N], dor[N], ans[N]; 
int n,m,k,s; 

void dfs2(int r, int v, bool add){ // dor 
     if (v > n) return; 
     dor[dist[v]-dist[r]+s] += (add ? 1 : -1); 
     for(int u : g[v]) dfs2(r,u,add);
}

void dfs(int v){
     if (v <= n){
          jad.pb(v); 
          dfs2(v,v,1);
          for(int u : g[v]) dfs(u); 
          dfs2(v,v,0); 
          jad.pop_back();
     }
     else{
          // ziad
          for(int par : jad){ // az koja mastaghim oomadim
               int hav = dist[v] - dist[par] + s; 
               if (k-hav >= 0 && mos[k-hav]) ans[v-n] = 1; 
          }
          // kam
          int rem = k - dist[v]; 
          for(int i=1; i*i <= rem; i++){
               if (rem%i) continue; 
               if (dor[rem/i] || dor[rem/(rem/i)]) ans[v-n] = 1; 
          }
     }
}

int32_t main(){
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

     cin >> n >> m >> k >> s; s++;
     dist[0] = 1;
     mos[1] = 1;  
     for(int i=1; i<=n; i++){
          int fa, megh; cin >> fa >> megh; 
          dist[i] = dist[fa] + megh + 1; 
          g[fa].pb(i); 
          mos[dist[i]] = 1; 
     }
     for(int i=n+1; i<=n+m; i++){
          int fa, megh; cin >> fa >> megh;
          dist[i] = dist[fa] + megh;  
          if (dist[i] == k) ans[i-n] = 1;
          g[fa].pb(i);
     }
     dfs(0); 
     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