# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
661232 |
2022-11-25T02:49:19 Z |
jiahng |
Valley (BOI19_valley) |
C++14 |
|
313 ms |
35328 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 100010
#define INF (ll)1e18
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
int N,S,Q,E,I,R;
int A[maxn], B[maxn], W[maxn], x;
bool shop[maxn];
vpi adj[maxn];
int co = 0;
int st[maxn], en[maxn], depth[maxn],sz[maxn];
int dp[maxn]; // min dist to go downwards from x to a shop
void dfs(int x, int p){
st[x] = co++;
sz[x] = 1;
if (shop[x]) dp[x] = 0;
else dp[x] = INF;
aFOR(i, adj[x]) if (i.f != p){
depth[i.f] = depth[x] + i.s;
dfs(i.f,x);
sz[x] += sz[i.f];
dp[x] = min(dp[x], dp[i.f] + i.s);
}
en[x] = co - 1;
}
namespace UFDS{
int p[maxn];
int fl(int x){
if (p[x] == x) return x;
return p[x] = fl(p[x]);
}
}
vpi queries[maxn];
int ans[maxn];
int C[maxn];
int dist[maxn], D[maxn];
priority_queue <pi> pq[maxn];
void dfs2(int x,int p){
int mx = -1;
aFOR(i, adj[x]) if (i.f != p){
dfs2(i.f, x);
if (mx == -1 || pq[mx].size() < pq[i.f].size()) mx = i.f;
}
if (mx != -1) pq[mx].swap(pq[x]);
pq[x].push(pi(C[x], x));
aFOR(i,adj[x]) if (i.f != p && i.f != mx){
while (!pq[i.f].empty()){
pq[x].push(pq[i.f].top()); pq[i.f].pop();
}
}
vi v;
while (!pq[x].empty() && pq[x].top().f >= C[x]){
v.pb(pq[x].top().s); pq[x].pop();
}
FOR(i,1,(int)v.size()-1){
int x = UFDS::fl(v[i]);
UFDS::p[x] = UFDS::fl(v[0]);
}
if (!v.empty()){
D[UFDS::fl(v[0])] = C[x]; pq[x].push(pi(C[x], UFDS::fl(v[0])));
}
aFOR(i, queries[x]){
ans[i.s] = D[UFDS::fl(i.f)] + depth[i.f];
}
}
int32_t main(){
cin >> N >> S >> Q >> E;
FOR(i,1,N-1){
cin >> A[i] >> B[i] >> W[i];
adj[A[i]].pb(pi(B[i], W[i]));
adj[B[i]].pb(pi(A[i], W[i]));
}
FOR(i,1,S){
cin >> x; shop[x] = 1;
}
dfs(E,-1);
FOR(i,1,N-1){
if (depth[A[i]] > depth[B[i]]) swap(A[i], B[i]); // A is the parent
}
FOR(i,1,Q){
cin >> I >> R;
if (!(st[B[I]] <= st[R] && st[R] <= en[B[I]])) ans[i] = -2;
else{
queries[B[I]].pb(pi(R, i));
}
}
FOR(i,1,N) C[i] = dp[i] - depth[i]; // defn of C
FOR(i,1,N) UFDS::p[i] = i;
dfs2(E,-1);
FOR(i,1,Q){
if (ans[i] == -2) cout << "escaped\n";
else if (ans[i] >= INF) cout << "oo\n";
else cout << ans[i] << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8532 KB |
Output is correct |
2 |
Correct |
8 ms |
8412 KB |
Output is correct |
3 |
Correct |
9 ms |
8416 KB |
Output is correct |
4 |
Correct |
8 ms |
8404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8532 KB |
Output is correct |
2 |
Correct |
8 ms |
8412 KB |
Output is correct |
3 |
Correct |
9 ms |
8416 KB |
Output is correct |
4 |
Correct |
8 ms |
8404 KB |
Output is correct |
5 |
Correct |
6 ms |
8404 KB |
Output is correct |
6 |
Correct |
6 ms |
8424 KB |
Output is correct |
7 |
Correct |
6 ms |
8420 KB |
Output is correct |
8 |
Correct |
6 ms |
8404 KB |
Output is correct |
9 |
Correct |
6 ms |
8404 KB |
Output is correct |
10 |
Correct |
7 ms |
8404 KB |
Output is correct |
11 |
Correct |
7 ms |
8380 KB |
Output is correct |
12 |
Correct |
6 ms |
8404 KB |
Output is correct |
13 |
Correct |
6 ms |
8460 KB |
Output is correct |
14 |
Correct |
6 ms |
8404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
277 ms |
33772 KB |
Output is correct |
2 |
Correct |
309 ms |
34612 KB |
Output is correct |
3 |
Correct |
313 ms |
33908 KB |
Output is correct |
4 |
Correct |
302 ms |
32800 KB |
Output is correct |
5 |
Correct |
277 ms |
32212 KB |
Output is correct |
6 |
Correct |
294 ms |
34448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8532 KB |
Output is correct |
2 |
Correct |
8 ms |
8412 KB |
Output is correct |
3 |
Correct |
9 ms |
8416 KB |
Output is correct |
4 |
Correct |
8 ms |
8404 KB |
Output is correct |
5 |
Correct |
6 ms |
8404 KB |
Output is correct |
6 |
Correct |
6 ms |
8424 KB |
Output is correct |
7 |
Correct |
6 ms |
8420 KB |
Output is correct |
8 |
Correct |
6 ms |
8404 KB |
Output is correct |
9 |
Correct |
6 ms |
8404 KB |
Output is correct |
10 |
Correct |
7 ms |
8404 KB |
Output is correct |
11 |
Correct |
7 ms |
8380 KB |
Output is correct |
12 |
Correct |
6 ms |
8404 KB |
Output is correct |
13 |
Correct |
6 ms |
8460 KB |
Output is correct |
14 |
Correct |
6 ms |
8404 KB |
Output is correct |
15 |
Correct |
277 ms |
33772 KB |
Output is correct |
16 |
Correct |
309 ms |
34612 KB |
Output is correct |
17 |
Correct |
313 ms |
33908 KB |
Output is correct |
18 |
Correct |
302 ms |
32800 KB |
Output is correct |
19 |
Correct |
277 ms |
32212 KB |
Output is correct |
20 |
Correct |
294 ms |
34448 KB |
Output is correct |
21 |
Correct |
253 ms |
34000 KB |
Output is correct |
22 |
Correct |
279 ms |
35268 KB |
Output is correct |
23 |
Correct |
276 ms |
32572 KB |
Output is correct |
24 |
Correct |
281 ms |
33240 KB |
Output is correct |
25 |
Correct |
266 ms |
35328 KB |
Output is correct |
26 |
Correct |
249 ms |
32348 KB |
Output is correct |
27 |
Correct |
264 ms |
31792 KB |
Output is correct |
28 |
Correct |
267 ms |
30392 KB |
Output is correct |
29 |
Correct |
280 ms |
30500 KB |
Output is correct |
30 |
Correct |
278 ms |
31464 KB |
Output is correct |
31 |
Correct |
244 ms |
30780 KB |
Output is correct |
32 |
Correct |
267 ms |
29844 KB |
Output is correct |
33 |
Correct |
265 ms |
29320 KB |
Output is correct |
34 |
Correct |
301 ms |
31312 KB |
Output is correct |
35 |
Correct |
270 ms |
34060 KB |
Output is correct |
36 |
Correct |
255 ms |
33728 KB |
Output is correct |