Submission #131954

#	Time	Username	Problem	Language	Result	Execution time	Memory
131954		E869120	Valley (BOI19_valley)	C++14	100 / 100	597 ms	38776 KiB

valley

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

class RangeAddMinSegmentTree {
public:
	vector<long long> dat, lazy; int size_ = 1;

	void init(int sz) {
		while (size_ <= sz) size_ *= 2;
		dat.resize(size_ * 2, 0);
		lazy.resize(size_ * 2, 0);
	}
	void refresh(int pos) {
		if (pos < size_) {
			lazy[pos * 2 + 0] += lazy[pos];
			lazy[pos * 2 + 1] += lazy[pos];
			lazy[pos] = 0;
			dat[pos] = min(dat[pos * 2] + lazy[pos * 2], dat[pos * 2 + 1] + lazy[pos * 2 + 1]);
		}
		else {
			dat[pos] += lazy[pos];
			lazy[pos] = 0;
		}
	}
	void add_(int l, int r, long long x, int a, int b, int u) {
		if (l <= a && b <= r) { lazy[u] += x; refresh(u); return; }
		if (r <= a || b <= l) return;

		add_(l, r, x, a, (a + b) >> 1, u * 2);
		add_(l, r, x, (a + b) >> 1, b, u * 2 + 1);
		refresh(u);
	}
	void add(int l, int r, long long x) {
		return add_(l, r, x, 0, size_, 1);
	}
	long long query_(int l, int r, int a, int b, int u) {
		refresh(u);
		if (l <= a && b <= r) return dat[u];
		if (r <= a || b <= l) return (1LL << 60);

		long long v1 = query_(l, r, a, (a + b) >> 1, u * 2);
		long long v2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		refresh(u);
		return min(v1, v2);
	}
	long long query(int l, int r) {
		return query_(l, r, 0, size_, 1);
	}
};

// -------------------------------- 変数 ---------------------------------------
int N, S, Q, E;
long long A[100009], B[100009], W[100009], dist[100009], ans[100009];
long long I[100009], R[100009];
bool used[100009];
vector<pair<int, long long>> X[100009], Y[100009];
vector<pair<int, int>> T[100009];
int cl[100009], cr[100009], cnts;

RangeAddMinSegmentTree Z;

// -------------------------------- 関数 ---------------------------------------

void dfs2(int pos, long long dep) {
	cnts++; cl[pos] = cnts; dist[pos] = dep;
	for (int i = 0; i < Y[pos].size(); i++) {
		if (cl[Y[pos][i].first] != 0) continue;
		X[pos].push_back(Y[pos][i]);
		dfs2(Y[pos][i].first, dep + Y[pos][i].second);
	}
	cr[pos] = cnts;
}

void dfs3(int pos) {
	for (int i = 0; i < X[pos].size(); i++) {
		Z.add(1, N + 1, X[pos][i].second);
		Z.add(cl[X[pos][i].first], cr[X[pos][i].first] + 1, -2LL * X[pos][i].second);

		dfs3(X[pos][i].first);

		Z.add(1, N + 1, -X[pos][i].second);
		Z.add(cl[X[pos][i].first], cr[X[pos][i].first] + 1, 2LL * X[pos][i].second);
	}

	/*cout << "pos = " << pos << endl;
	for (int i = 1; i <= N; i++) cout << min(99LL, Z.query(i, i + 1)) << " "; cout << endl;*/

	for (int i = 0; i < T[pos].size(); i++) {
		int id = T[pos][i].second;
		int pa = A[I[id]], pb = B[I[id]];
		if (dist[pa] > dist[pb]) swap(pa, pb);

		// 脱出可能かどうか判定
		bool I1 = false; if (cl[pb] <= cl[E] && cr[E] <= cr[pb]) I1 = true;
		bool I2 = false; if (cl[pb] <= cl[R[id]] && cr[R[id]] <= cr[pb]) I2 = true;

		if (I1 == I2) {
			ans[id] = -1;
		}
		else {
			if (I2 == true) {
				ans[id] = Z.query(cl[pb], cr[pb] + 1);
			}
			else {
				long long v1 = Z.query(1, cl[pb]);
				long long v2 = Z.query(cr[pb] + 1, N + 1);
				ans[id] = min(v1, v2);
			}
			if (ans[id] >= (1LL << 59)) ans[id] = (1LL << 60);
		}
	}
}

void solve_subtask3() {
	for (int i = 1; i <= N - 1; i++) {
		scanf("%lld%lld%lld", &A[i], &B[i], &W[i]);
		Y[A[i]].push_back(make_pair(B[i], W[i]));
		Y[B[i]].push_back(make_pair(A[i], W[i]));
	}
	dfs2(1, 0);
	for (int i = 1; i <= S; i++) {
		int t; scanf("%d", &t);
		used[t] = true;
	}
	for (int i = 1; i <= Q; i++) {
		scanf("%d%d", &I[i], &R[i]);
		T[R[i]].push_back(make_pair(I[i], i));
	}

	Z.init(N + 2);
	for (int i = 1; i <= N; i++) Z.add(cl[i], cl[i] + 1, dist[i]);
	for (int i = 1; i <= N; i++) { if (used[i] == false) Z.add(cl[i], cl[i] + 1, (1LL << 60)); }

	dfs3(1);

	for (int i = 1; i <= Q; i++) {
		if (ans[i] == -1) printf("escaped\n");
		else if (ans[i] == (1LL << 60)) printf("oo\n");
		else printf("%lld\n", ans[i]);
	}
}

int main() {
	scanf("%d%d%d%d", &N, &S, &Q, &E);
	solve_subtask3();
	return 0;
}

Compilation message (stderr)

valley.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
valley.cpp: In function 'void dfs2(int, long long int)':
valley.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Y[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
valley.cpp: In function 'void dfs3(int)':
valley.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
valley.cpp:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < T[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
valley.cpp: In function 'void solve_subtask3()':
valley.cpp:129:29: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   scanf("%d%d", &I[i], &R[i]);
                 ~~~~~       ^
valley.cpp:129:29: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
valley.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &A[i], &B[i], &W[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:125:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int t; scanf("%d", &t);
          ~~~~~^~~~~~~~~~
valley.cpp:129:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &I[i], &R[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:147: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);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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