Submission #237891

#	Time	Username	Problem	Language	Result	Execution time	Memory
237891		grt	Valley (BOI19_valley)	C++17	100 / 100	394 ms	26104 KiB

valley

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

struct Query {
	int id, block;
};

struct Edge {
	int v, cost, id;
};

struct Node {
	ll f, g;
};

const int nax = 100 * 1000 + 10;
const ll INF = (ll)1e16+10;
int n,q,s,root,nr;
int in[nax], out[nax];
int edge_block[nax];
ll dist[nax];
bool is_shop[nax];
vector<Query>qr[nax];
vector<Edge>V[nax];
Node T[(1<<19)];
ll ans[nax];

void propagate(int x) {
	T[2*x].g += T[x].g;
	T[2*x+1].g += T[x].g;
	T[x].g = 0;
}

void coutTree(int l, int r, int v) {
	cout << v << " " << l << " " << r << " : " << T[v].f << " " << T[v].g << "\n";
	if(l==r) return;
	int mid = (l+r)/2;
	coutTree(l, mid, v*2);
	coutTree(mid+1,r,v*2+1);
}

void update(int a,int b, ll x, int l, int r, int v) {
	//~ cout << a << " " << b << ": "<<l << " " << r << "\n";
	if(a <= l && r <= b) {
		T[v].g += x;
		return;
	}
	propagate(v);
	int mid = (l+r)/2;
	if(a <= mid) update(a,b,x,l,mid,v*2);
	if(mid < b) update(a,b,x,mid+1,r,v*2+1);
	T[v].f = min(T[2*v].f + T[2*v].g, T[2*v+1].f + T[2*v+1].g);
}

ll query(int a,int b,int l, int r, int v) {
	//~ cout << l << " " << r << "\n";
	if(a <= l && r <= b) {
		return T[v].f + T[v].g;
	}
	propagate(v);
	int mid = (l+r)/2;
	ll w = INF;
	if(a <= mid) w = min(w, query(a,b,l,mid,v*2));
	if(mid < b) w = min(w, query(a,b,mid+1,r,v*2+1));
	T[v].f = min(T[2*v].f + T[2*v].g, T[2*v+1].f + T[2*v+1].g);
	return w + T[v].g;
}


void dfs(int x, int p) {
	in[x] = nr++;
	for(auto nbh : V[x]) {
		if(nbh.v != p) {
			edge_block[nbh.id] = nbh.v;
			dist[nbh.v] = dist[x] + nbh.cost;
			dfs(nbh.v, x);
		}
	}
	out[x] = nr;
}

void dfsAns(int x,int p) {
	//~ cout << x << ":::::::\n";
	//~ coutTree(0, n-1, 1);
	for(auto qre : qr[x]) {
		int v = edge_block[qre.block];
		if(in[v] <= in[x] && in[x] <= out[v] - 1) {
			//~ cout << "X\n";
			ll d = query(in[v], out[v] - 1, 0, n-1, 1);
			//~ coutTree(0,n-1,1);
			//~ if(d == -8) coutTree(0, n-1, 1);
			//~ cout << x << " " << in[v] << " " << out[v] << " : " << d << "\n";
			
			//~ cout << "D : "<<d << "\n";
			ans[qre.id] = d;
		} else {
			ans[qre.id] = -1;
		}
	}
	//~ cout << x << "\n";
	for(auto nbh : V[x]) {
		if(nbh.v != p) {
			//~ cout << in[nbh.v] << " " << out[nbh.v] << "\n";
			
			update(in[nbh.v], out[nbh.v] - 1, -2 * nbh.cost, 0, n-1, 1);
			update(0, n-1, nbh.cost, 0, n-1, 1);
			dfsAns(nbh.v, x);
			update(in[nbh.v], out[nbh.v] - 1, 2 * nbh.cost, 0, n-1, 1);
			update(0, n-1, -nbh.cost, 0, n-1, 1);
		}
	}
}

void init(int l, int r, int v) {
	if(l == r) {
		return;
	}
	init(l, (l+r)/2, v*2);
	init((l+r)/2 + 1, r, v*2+1);
	T[v].f = min(T[2*v].f + T[2*v].g, T[2*v+1].f + T[2*v+1].g);
}

int main() {_
	cin >> n >> s >> q >> root;
	for(int a,b,w,i=1; i < n; ++i) {
		cin >> a >> b >> w;
		V[a].PB({b,w,i});
		V[b].PB({a,w,i});
	}
	for(int a,i = 1; i <= s; ++i) {
		cin >> a;
		is_shop[a] = 1;
	}
	for(int a,b,i=1; i<= q; ++i) {
		cin >> a >> b;
		qr[b].PB({i,a});
	}
	dfs(root, 0);
	//~ for(int i = 1; i <= 2 * n; ++i) {
		//~ T[i].f = INF;
	//~ }
	for(int i = 1; i <= n; ++i) {
		//~ cout << "I : " << in[i] << " " << out[i] << "\n";
		if(is_shop[i]) {
			update(in[i],in[i],dist[i], 0, n-1, 1);
		} else {
			update(in[i],in[i], INF, 0, n-1, 1);
		}
	}
	
	dfsAns(root, 0);
	for(int i = 1; i <= q; ++i) {
		if(ans[i] == -1) {
			cout << "escaped\n";
		} else if(ans[i] > (ll)1e14) {
			cout << "oo\n";
		} else {
			cout << ans[i] << "\n";
		}
	}
	
}

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