Submission #131947

#	Time	Username	Problem	Language	Result	Execution time	Memory
131947		E869120	Valley (BOI19_valley)	C++14	36 / 100	3030 ms	17084 KiB

valley

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

int N, S, Q, E;
long long A[100009], B[100009], W[100009], dist[100009];
bool used[100009];

vector<pair<int, long long>> X[100009];
vector<int> Y[100009];
int cl[100009], cr[100009], cnts;

void dfs(int pos, long long dep) {
	if (dist[pos] != (1LL << 60)) return;
	dist[pos] = dep;
	for (int i = 0; i < X[pos].size(); i++) {
		dfs(X[pos][i].first, dep + X[pos][i].second);
	}
}

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

void solve(int I, int R) {
	for (int i = 1; i <= N; i++) { X[i].clear(); dist[i] = (1LL << 60); }
	for (int i = 1; i <= N - 1; i++) {
		if (i == I) continue;
		X[A[i]].push_back(make_pair(B[i], W[i]));
		X[B[i]].push_back(make_pair(A[i], W[i]));
	}
	dfs(R, 0);

	if (dist[E] != (1LL << 60)) {
		printf("escaped\n");
		return;
	}

	long long minx = (1LL << 60);
	for (int i = 1; i <= N; i++) {
		if (used[i] == true) minx = min(minx, dist[i]);
	}
	if (minx == (1LL << 60)) {
		printf("oo\n");
	}
	else {
		printf("%lld\n", minx);
	}
}

void solve2(int I, int R) {
	int pa = A[I], pb = B[I];
	if (dist[pa] > dist[pb]) swap(pa, pb);

	bool I1 = false; if (cl[pb] <= cl[R] && cr[R] <= cr[pb]) I1 = true;
	bool I2 = false; if (cl[pb] <= cl[E] && cr[E] <= cr[pb]) I2 = true;
	
	if (I1 == I2) {
		printf("escaped\n");
	}
	else {
		printf("0\n");
	}
}

void solve_subtask1() {
	for (int i = 1; i <= N - 1; i++) {
		scanf("%lld%lld%lld", &A[i], &B[i], &W[i]);
	}
	for (int i = 1; i <= S; i++) {
		int t; scanf("%d", &t);
		used[t] = true;
	}
	for (int i = 1; i <= Q; i++) {
		int I, R; scanf("%d%d", &I, &R);
		solve(I, R);
	}
}

void solve_subtask2() {
	for (int i = 1; i <= N - 1; i++) {
		scanf("%lld%lld%lld", &A[i], &B[i], &W[i]);
		Y[A[i]].push_back(B[i]);
		Y[B[i]].push_back(A[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++) {
		int I, R; scanf("%d%d", &I, &R);
		solve(I, R);
	}
}

int main() {
	scanf("%d%d%d%d", &N, &S, &Q, &E);
	if (N <= 1000) {
		solve_subtask1();
	}
	else {
		solve_subtask2();
	}
	return 0;
}

Compilation message (stderr)

valley.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
valley.cpp: In function 'void dfs(int, long long int)':
valley.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
valley.cpp: In function 'void dfs2(int, int)':
valley.cpp:25: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 solve_subtask1()':
valley.cpp:75: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:78: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:82:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int I, R; scanf("%d%d", &I, &R);
             ~~~~~^~~~~~~~~~~~~~~~
valley.cpp: In function 'void solve_subtask2()':
valley.cpp:89: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:95: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:99:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int I, R; scanf("%d%d", &I, &R);
             ~~~~~^~~~~~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:105: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: 0 / 23
• Subtask 4: 0 / 41