# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
131954 |
2019-07-18T05:59:45 Z |
E869120 |
Valley (BOI19_valley) |
C++14 |
|
597 ms |
38776 KB |
#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
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
7800 KB |
Output is correct |
2 |
Correct |
13 ms |
7848 KB |
Output is correct |
3 |
Correct |
12 ms |
7900 KB |
Output is correct |
4 |
Correct |
13 ms |
7800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
7800 KB |
Output is correct |
2 |
Correct |
13 ms |
7848 KB |
Output is correct |
3 |
Correct |
12 ms |
7900 KB |
Output is correct |
4 |
Correct |
13 ms |
7800 KB |
Output is correct |
5 |
Correct |
10 ms |
7548 KB |
Output is correct |
6 |
Correct |
11 ms |
7544 KB |
Output is correct |
7 |
Correct |
11 ms |
7672 KB |
Output is correct |
8 |
Correct |
13 ms |
7664 KB |
Output is correct |
9 |
Correct |
11 ms |
7640 KB |
Output is correct |
10 |
Correct |
11 ms |
7672 KB |
Output is correct |
11 |
Correct |
11 ms |
7672 KB |
Output is correct |
12 |
Correct |
11 ms |
7672 KB |
Output is correct |
13 |
Correct |
11 ms |
7672 KB |
Output is correct |
14 |
Correct |
11 ms |
7672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
458 ms |
28344 KB |
Output is correct |
2 |
Correct |
488 ms |
28068 KB |
Output is correct |
3 |
Correct |
496 ms |
28176 KB |
Output is correct |
4 |
Correct |
548 ms |
31396 KB |
Output is correct |
5 |
Correct |
448 ms |
30072 KB |
Output is correct |
6 |
Correct |
535 ms |
37368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
7800 KB |
Output is correct |
2 |
Correct |
13 ms |
7848 KB |
Output is correct |
3 |
Correct |
12 ms |
7900 KB |
Output is correct |
4 |
Correct |
13 ms |
7800 KB |
Output is correct |
5 |
Correct |
10 ms |
7548 KB |
Output is correct |
6 |
Correct |
11 ms |
7544 KB |
Output is correct |
7 |
Correct |
11 ms |
7672 KB |
Output is correct |
8 |
Correct |
13 ms |
7664 KB |
Output is correct |
9 |
Correct |
11 ms |
7640 KB |
Output is correct |
10 |
Correct |
11 ms |
7672 KB |
Output is correct |
11 |
Correct |
11 ms |
7672 KB |
Output is correct |
12 |
Correct |
11 ms |
7672 KB |
Output is correct |
13 |
Correct |
11 ms |
7672 KB |
Output is correct |
14 |
Correct |
11 ms |
7672 KB |
Output is correct |
15 |
Correct |
458 ms |
28344 KB |
Output is correct |
16 |
Correct |
488 ms |
28068 KB |
Output is correct |
17 |
Correct |
496 ms |
28176 KB |
Output is correct |
18 |
Correct |
548 ms |
31396 KB |
Output is correct |
19 |
Correct |
448 ms |
30072 KB |
Output is correct |
20 |
Correct |
535 ms |
37368 KB |
Output is correct |
21 |
Correct |
489 ms |
28156 KB |
Output is correct |
22 |
Correct |
509 ms |
31352 KB |
Output is correct |
23 |
Correct |
569 ms |
31488 KB |
Output is correct |
24 |
Correct |
597 ms |
33640 KB |
Output is correct |
25 |
Correct |
586 ms |
38776 KB |
Output is correct |
26 |
Correct |
479 ms |
31480 KB |
Output is correct |
27 |
Correct |
507 ms |
31728 KB |
Output is correct |
28 |
Correct |
511 ms |
31608 KB |
Output is correct |
29 |
Correct |
550 ms |
34680 KB |
Output is correct |
30 |
Correct |
560 ms |
36984 KB |
Output is correct |
31 |
Correct |
487 ms |
30360 KB |
Output is correct |
32 |
Correct |
505 ms |
28408 KB |
Output is correct |
33 |
Correct |
515 ms |
28536 KB |
Output is correct |
34 |
Correct |
570 ms |
31308 KB |
Output is correct |
35 |
Correct |
554 ms |
35164 KB |
Output is correct |
36 |
Correct |
544 ms |
34184 KB |
Output is correct |