Submission #147259

#	Time	Username	Problem	Language	Result	Execution time	Memory
147259		tincamatei	Valley (BOI19_valley)	C++14	100 / 100	388 ms	30128 KiB

valley

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000;
const int MAX_Q = 100000;
const long long INF = 1LL << 60;

struct Edge {
	int a, b, cost;

	int other(int x) {
		return a ^ b ^ x;
	}
} edges[MAX_N - 1];

vector<int> graph[1+MAX_N];

int lastid;
int firstT[1+MAX_N], lastT[1+MAX_N];
long long depth[1+MAX_N], depthEuler[1+MAX_N];
bool shop[1+MAX_N], shopEuler[1+MAX_N], blockedEdge[1+MAX_N];

void predfs(int nod, int papa = -1) {
	++lastid;
	firstT[nod] = lastid;
	if(shop[nod]) {
		shopEuler[lastid] = true;
		depthEuler[lastid] = depth[nod];
	} else
		depthEuler[lastid] = INF;
	for(auto it: graph[nod]) {
		int son = edges[it].other(nod);
		int w   = edges[it].cost;

		if(son != papa) {
			depth[son] = depth[nod] + w;
			predfs(son, nod);
		}
	}
	lastT[nod] = lastid;
}

struct SegTree {
	long long aint[1+4*MAX_N], lazy[1+4*MAX_N];

	void init(int l = 1, int r = MAX_N, int nod = 1) {
		lazy[nod] = 0;
		if(l == r)
			aint[nod] = depthEuler[l];
		else if(l < r) {
			int mid = (l + r) / 2;
			init(l, mid, 2 * nod);
			init(mid + 1, r, 2 * nod + 1);
			aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
		}
	}

	void pushLazy(int nod, int l, int r) {
		if(aint[nod] == INF)
			lazy[nod] = 0;
		else {
			aint[nod] += lazy[nod];
			if(l < r) {
				lazy[2 * nod] += lazy[nod];
				lazy[2 * nod + 1] += lazy[nod];
			}
			lazy[nod] = 0;
		}
	}

	void update(int i, int j, int val, int l = 1, int r = MAX_N, int nod = 1) {
		pushLazy(nod, l, r);
		if(j < l || r < i || j < i) return;

		if(i <= l && r <= j) {
			lazy[nod] += val;
			pushLazy(nod, l, r);
		} else {
			int mid = (l + r) / 2;
			update(i, j, val, l, mid, 2 * nod);
			update(i, j, val, mid + 1, r, 2 * nod + 1);
			aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
		}
	}

	long long query(int i, int j, int l = 1, int r = MAX_N, int nod = 1) {
		pushLazy(nod, l, r);
		if(j < l || r < i || j < i) return INF;

		if(i <= l && r <= j)
			return aint[nod];
		else {
			int mid = (l + r) / 2;
			return min(query(i, j, l, mid, 2 * nod),
			           query(i, j, mid + 1, r, 2 * nod + 1));
		}
	}
} aint;

struct Query {
	int I;
	long long *rez;
};

vector<Query> query[1+MAX_N];
long long rez[MAX_Q];

void maindfs(int nod, int papa = 0) {
	for(auto it: query[nod]) {
		if(blockedEdge[it.I]) {
			int lowerNode;
			if(depth[edges[it.I].a] > depth[edges[it.I].b])
				lowerNode = edges[it.I].a;
			else
				lowerNode = edges[it.I].b;

			(*it.rez) = aint.query(firstT[lowerNode], lastT[lowerNode]);
		} else
			(*it.rez) = -1;
	}

	for(auto it: graph[nod]) {
		int son, w;
		son = edges[it].other(nod);
		w   = edges[it].cost;

		if(son != papa) {
			aint.update(1, MAX_N, w);
			aint.update(firstT[son], lastT[son], -2 * w);
			blockedEdge[it] = true;
			maindfs(son, nod);
			aint.update(1, MAX_N, -w);
			aint.update(firstT[son], lastT[son], 2 * w);
			blockedEdge[it] = false;
		}
	}
}

int main() {
	int N, S, Q, E;
	
	scanf("%d%d%d%d", &N, &S, &Q, &E);
	for(int i = 0; i < N - 1; ++i) {
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		edges[i] = {a, b, w};
		graph[a].push_back(i);
		graph[b].push_back(i);
	}

	for(int i = 0; i < S; ++i) {
		int x;
		scanf("%d", &x);
		shop[x] = true;
	}

	for(int i = 0; i < Q; ++i) {
		int I, R;
		scanf("%d%d", &I, &R);
		query[R].push_back(Query{I - 1, &rez[i]});
	}

	predfs(E);
	aint.init();
	maindfs(E);

	for(int i = 0; i < Q; ++i) {
		if(rez[i] == -1)
			printf("escaped\n");
		else if(rez[i] >= INF)//100000000000000LL)
			printf("oo\n");
		else
			printf("%lld\n", rez[i]);
	}

	return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &N, &S, &Q, &E);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
valley.cpp:160:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &I, &R);
   ~~~~~^~~~~~~~~~~~~~~~

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