Submission #1276805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276805		behesht	File Paths (BOI15_fil)	C++20	100 / 100	736 ms	173204 KiB

fil

#include <bits/stdc++.h>

#define d1(x)                cout << #x << " : " << x << endl << flush
#define d2(x, y)             cout << #x << " : " << x << "   " << #y << " : " << y << endl << flush
#define d3(x, y, z)          cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define d4(x, y, z, a)       cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define arr(x)               array <ll, x>
#define ld                   long double
#define ll                   long long
#define int                  long long
#define pb                   push_back
#define endl                 '\n'
#define lc                   v << 1
#define rc                   v << 1 | 1

using namespace std;

const int INF = 1e18 + 24 + (34 / 10); // 34 ---> 35
const int MAXN = 6e3 + 24 + (34 / 10); // 34 ---> 35

string Ans[2] = {"NO", "YES"};

int n, m, k, t;
int len[MAXN], p[MAXN], dp[MAXN], ans[MAXN];
int tim, tin[MAXN], tout[MAXN];
vector <int> adj[MAXN], arr;
vector <arr(2)> c[1000005];
vector <arr(3)> s[MAXN];

void leaf(int u){

	int x = k - dp[u];
	s[u].pb({x, u, 0});

	if(!x){
		ans[u] = 1;
		return;
	}
	
	// d3(u, dp[u], x);

	for(int i = 1; i * i <= x; i++){
		if(x % i == 0){
			c[i].pb({tin[u], 0});
			c[x / i].pb({tin[u], 0});
		}
	}

	// cout << endl;
}

void dfs(int u, int par){

	tin[u] = ++tim;
	// d2(u, tin[u]);
	arr.pb(u);

	if(u != 0){
		dp[u] = dp[par] + len[u] + 1;
		// d4(u, p[u], par, dp[u]);
	}

	for(auto v : adj[u]){
		if(v != par){
			dfs(v, u);

			for(auto x : s[v])
				s[u].pb(x);
		}
	}

	if(u > n)
		leaf(u);

	sort(s[u].begin(), s[u].end());
	tout[u] = tim;
}

bool is(int x, int p){
	return (tin[p] <= tin[x] && tin[x] <= tout[p]);
}

void Hal1(int u, int v){

	int x = dp[u] - dp[v] + t + 1;
	
	// d3(u, v, x);

	arr(3) val1 = {x, -INF, -INF};
	arr(3) val2 = {x, INF, INF};

	int ind1 = lower_bound(s[v].begin(), s[v].end(), val1) - s[v].begin();
	int ind2 = upper_bound(s[v].begin(), s[v].end(), val2) - s[v].begin();

	if(s[v][ind1][0] > x)
		return;	

	s[v][ind1][2]++;
	s[v][ind2][2]--;
}

void Hal2(int u, int v){
 
	int x = dp[u] - dp[v] + t + 1;
 
	if(x > 1000000)
		return;
	
	arr(2) val1 = {tin[v], -INF};
	arr(2) val2 = {tout[v], INF};
 
	auto it1 = lower_bound(c[x].begin(), c[x].end(), val1);
	auto it2 = upper_bound(c[x].begin(), c[x].end(), val2);
 
	auto [t1, _] = *it1;
	auto [t2, __] = *it2;
 
	if(t1 > tout[v])
		return;
 
	int ind1 = it1 - c[x].begin();
	int ind2 = it2 - c[x].begin();

	c[x][ind1][1]++;	
	c[x][ind2][1]--;
}

signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k >> t;

	for(int i = 1; i <= n + m; i++){
		cin >> p[i] >> len[i];

		adj[p[i]].pb(i);	
		adj[i].pb(p[i]);
	}
	
	arr.pb(0);
	dfs(0, 0);
	
	for(int i = 0; i <= 1000000; i++)
		c[i].pb({INF, INF});
	
	for(int i = 0; i <= n + m; i++)
		s[i].pb({INF, INF, INF});

	for(int u = 0; u <= n; u++){
		for(int v = 0; v <= n; v++){
		
			if(!is(u, v))
				Hal1(u, v);
			
			if(is(u, v)) 
				Hal2(u, v);
		}
	}

	// cccccccc
	for(int i = 0; i <= 1000000; i++){
		int eli = 0;
 
		for(auto [tm, x] : c[i]){
 
			if(tm == INF)
				continue;
			
			int ind = arr[tm];
			eli += x;
 
			if(eli > 0)
				ans[ind] = 1;
		}
	}

	// ssssssss
	for(int i = 0; i <= n + m; i++){
		int eli = 0;

		for(auto [val, ind, x] : s[i]){

			if(val == INF)
				continue;

			eli += x;

			if(eli > 0)
				ans[ind] = 1;
		}
	}

	for(int i = n + 1; i <= n + m; i++)
		cout << Ans[ans[i]] << endl;
}

// Ey To Bahane! :_)))

// -------------<3------------- //
/*
Magasan dor shirini: 

1. MAXN
2. Input style
3. index or value? Masale In Ast!	
4. MOD 

*/

/*
3 5 274855
0

0 2
1 4
2 8

3 1
1 1
2 1
1 1
2 1
*/

• Subtask 1: 33 / 33
• Subtask 2: 33 / 33
• Subtask 3: 34 / 34