Submission #379797

#	Time	Username	Problem	Language	Result	Execution time	Memory
379797		SavicS	Valley (BOI19_valley)	C++14	100 / 100	561 ms	45676 KiB

valley

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,ll> pii;
const int maxn = 100005;
const ll inf = 1e18 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, q, k, R;
pii niz[maxn];

vector<pii> g[maxn];

bool mark[maxn];

int d[maxn];
ll dist[maxn];
ll kol[maxn];
void dfs1(int v, int p){
	if(mark[v])kol[v] = 0;
	else kol[v] = inf;
	for(auto c : g[v]){
		int u = c.fi;
		ll w = c.se;
		if(u != p){
			d[u] = d[v] + 1;
			dist[u] = dist[v] + w;
			dfs1(u, v);
			kol[v] = min(kol[v], w + kol[u]);
		}
	}
}

ll dud[maxn];
void upd(int x, ll val){
	while(x <= maxn){
		dud[x] += val;
		x += x&(-x);
	}
}
ll query(int x){
	ll sum = 0;
	while(x > 0){
		sum += dud[x];
		x -= x&(-x);
	}
	return sum;
}

int timer = 0;
int in[maxn];
int out[maxn];
int deda[maxn][20];
ll mn[maxn][20];
void dfs2(int v, int p, ll pw){
	in[v] = ++timer;
	if(mark[v])upd(in[v], 1);
	deda[v][0] = p;
	mn[v][0] = pw;
	ff(i,1,19){
		deda[v][i] = deda[deda[v][i - 1]][i - 1];
		mn[v][i] = min(mn[v][i - 1], mn[deda[v][i - 1]][i - 1]);
	}
	for(auto c : g[v]){
		int u = c.fi;
		ll w = c.se;
		if(u != p){
			dfs2(u, v, (kol[v] == inf ? inf : kol[v] - dist[v]));
		}
	}
	out[v] = timer;
}

bool predak(int x, int y){
	return (in[x] <= in[y] && out[x] >= out[y]);
}

ll calc(int x, int y){
	ll najm = inf;
	fb(i,19,0){
		if(y & (1 << i)){
			najm = min(najm, mn[x][i]);
			x = deda[x][i];
		}
	}
	return najm;
}

int main()
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
	cin >> n >> k >> q >> R;
	ff(i,1,n - 1){
		int u, v;
		ll w;
		cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
		niz[i] = {u, v};
	}
	ff(i,1,k){
		int x;
		cin >> x;
		mark[x] = 1;
	}
	dfs1(R, -1);
	dfs2(R, -1, 0);
	while(q--){
		int id, s;
		cin >> id >> s;
		int u = niz[id].fi;
		int v = niz[id].se;
		if(d[u] < d[v])swap(u, v);
		// 1 - slucaj, ako je izvan subtree-a u
		if(!predak(u, s)){
			cout << "escaped" << endl;
			continue;
		}
		// nema valley u subtree od u
		if(query(out[u]) - query(in[u] - 1) == 0){
			cout << "oo" << endl;
			continue;
		}
		ll dole = kol[s];
		ll gore = calc(s, d[s] - d[u]) + dist[s];
		cout << min(dole, gore) << endl;
	}
    return 0;
}
/**

5 1 5 1
1 2 1 
2 3 1
3 4 1 
4 5 1
5
2 3
2 4
2 5

5 2 3 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4


// probati bojenje sahovski ili slicno

**/

Compilation message (stderr)

valley.cpp: In function 'void dfs2(int, int, ll)':
valley.cpp:84:6: warning: unused variable 'w' [-Wunused-variable]
   84 |   ll w = c.se;
      |      ^

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41