# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
952423 |
2024-03-23T20:35:50 Z |
RadicaI |
Valley (BOI19_valley) |
C++17 |
|
297 ms |
54352 KB |
#include <bits/stdc++.h>
#define int long long
#define pi pair<int,int>
#define pb push_back
#define V vector
#define vi V<int>
#define mi map<int,int>
#define MOD 1000000007
#define MOD2 998244353
#define mp make_pair
#define ins insert
#define qi queue<int>
#define pqi priority_queue<int>
#define si set<int>
#define v2i V<vi>
#define v3i V<v2i>
#define v4i V<v3i>
#define v5i V<v4i>
#define INF 1e18
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl "\n"
#define lb lower_bound
#define ub upper_bound
#define print(x) cout << x<<" ";
#define vpi V<pi>
#define Y cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define msi multiset<int>
#define F first
#define S second
#define ld long double
#define RE return;
#define IMP cout<<-1<<endl;return;
using namespace std;
template <typename T>
std::istream& operator>>(std::istream& in, std::vector<T>& vec) {
for (T& x : vec) {
in >> x;
}
return in;
}
V<vpi> adj;
v2i bin;
v2i bin2;
int n;
vi dist; vi depth;
vi good;
vi best;
vi val;
const int mx = 17;
void dfs(int node, int x){
bin[node][0] = x;
if(good[node]) best[node] = dist[node];
for(int i=1; i<mx; i++) bin[node][i] = bin[bin[node][i-1]][i-1];
for(auto &y: adj[node])if(y.F!=x){
depth[y.F] = depth[node]+1;
dist[y.F] = dist[node] + y.S;
dfs(y.F, node);
best[node] = min(best[node], best[y.F]);
}
val[node] = (best[node] == INF ? INF : best[node] - 2*dist[node]);
bin2[node][0] = val[node];
}
int kth(int x, int k){
for(int i=0; i<mx; i++)if((1<<i)&k) x = bin[x][i];
return x;
}
int isAncestor(int a, int anc){
if(depth[a] <depth[anc] ) return 0;
else return kth(a, depth[a]-depth[anc]) == anc;
}
int lca(int x, int y){
if(depth[x]>depth[y]) swap(x,y);
y = kth(y, depth[y]-depth[x]);
if(x==y) return x;
for(int i=mx-1; i>=0; i--){
if(bin[x][i] != bin[y][i]) x = bin[x][i], y = bin[y][i];
}
return bin[x][0];
}
signed main(){
fastio;
int s,q,e;cin>>n>>s>>q>>e; e--;
adj.resize(n); bin = v2i(n, vi(mx)); bin2 = v2i(n, vi(mx));
dist.resize(n,0); depth.resize(n,0); good.resize(n,0); best.resize(n,INF); val.resize(n,INF);
vpi edgs(n-1);
for(int i=1; i<n; i++){
int a,b,w; cin>>a>>b>>w; a--;b--;
adj[a].pb({b,w});
adj[b].pb({a,w});
edgs[i-1] = {a,b};
}
for(int i=0; i<s; i++){
int k; cin >> k;
good[k-1]=1;
}
dfs(e,e);
for(auto &x: edgs)if(depth[x.F] > depth[x.S]) swap(x.F,x.S);
for(int i=1; i<mx; i++)for(int j=0; j<n; j++) bin2[j][i] = min(bin2[j][i-1], bin2[bin[j][i-1]][i-1]);
while(q--){
int i,r; cin>>i>>r; i--; r--;
int token = edgs[i].S;
if(!isAncestor(r, token)){
cout<<"escaped"<<endl;
continue;
}
int jump = depth[r] - depth[token]+1;
int ans = INF; int prev = dist[r];
for(int j=0; j<mx; j++)if((1<<j) & jump) ans = min(ans, bin2[r][j]), r = bin[r][j];
if(ans==INF) cout<<"oo"<<endl;
else cout <<ans+prev<<endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
604 KB |
Output is correct |
2 |
Correct |
3 ms |
604 KB |
Output is correct |
3 |
Correct |
2 ms |
604 KB |
Output is correct |
4 |
Correct |
2 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
604 KB |
Output is correct |
2 |
Correct |
3 ms |
604 KB |
Output is correct |
3 |
Correct |
2 ms |
604 KB |
Output is correct |
4 |
Correct |
2 ms |
604 KB |
Output is correct |
5 |
Correct |
2 ms |
860 KB |
Output is correct |
6 |
Correct |
2 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
856 KB |
Output is correct |
8 |
Correct |
1 ms |
860 KB |
Output is correct |
9 |
Correct |
2 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
2 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
860 KB |
Output is correct |
13 |
Correct |
1 ms |
856 KB |
Output is correct |
14 |
Correct |
1 ms |
856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
180 ms |
50772 KB |
Output is correct |
2 |
Correct |
191 ms |
50636 KB |
Output is correct |
3 |
Correct |
203 ms |
50772 KB |
Output is correct |
4 |
Correct |
235 ms |
52196 KB |
Output is correct |
5 |
Correct |
222 ms |
52816 KB |
Output is correct |
6 |
Correct |
297 ms |
54100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
604 KB |
Output is correct |
2 |
Correct |
3 ms |
604 KB |
Output is correct |
3 |
Correct |
2 ms |
604 KB |
Output is correct |
4 |
Correct |
2 ms |
604 KB |
Output is correct |
5 |
Correct |
2 ms |
860 KB |
Output is correct |
6 |
Correct |
2 ms |
860 KB |
Output is correct |
7 |
Correct |
1 ms |
856 KB |
Output is correct |
8 |
Correct |
1 ms |
860 KB |
Output is correct |
9 |
Correct |
2 ms |
860 KB |
Output is correct |
10 |
Correct |
1 ms |
860 KB |
Output is correct |
11 |
Correct |
2 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
860 KB |
Output is correct |
13 |
Correct |
1 ms |
856 KB |
Output is correct |
14 |
Correct |
1 ms |
856 KB |
Output is correct |
15 |
Correct |
180 ms |
50772 KB |
Output is correct |
16 |
Correct |
191 ms |
50636 KB |
Output is correct |
17 |
Correct |
203 ms |
50772 KB |
Output is correct |
18 |
Correct |
235 ms |
52196 KB |
Output is correct |
19 |
Correct |
222 ms |
52816 KB |
Output is correct |
20 |
Correct |
297 ms |
54100 KB |
Output is correct |
21 |
Correct |
159 ms |
50220 KB |
Output is correct |
22 |
Correct |
182 ms |
50024 KB |
Output is correct |
23 |
Correct |
201 ms |
50180 KB |
Output is correct |
24 |
Correct |
226 ms |
51952 KB |
Output is correct |
25 |
Correct |
246 ms |
54352 KB |
Output is correct |
26 |
Correct |
161 ms |
50316 KB |
Output is correct |
27 |
Correct |
196 ms |
50088 KB |
Output is correct |
28 |
Correct |
197 ms |
50320 KB |
Output is correct |
29 |
Correct |
222 ms |
51432 KB |
Output is correct |
30 |
Correct |
277 ms |
52720 KB |
Output is correct |
31 |
Correct |
156 ms |
50260 KB |
Output is correct |
32 |
Correct |
173 ms |
50004 KB |
Output is correct |
33 |
Correct |
223 ms |
50512 KB |
Output is correct |
34 |
Correct |
222 ms |
51796 KB |
Output is correct |
35 |
Correct |
246 ms |
54352 KB |
Output is correct |
36 |
Correct |
214 ms |
51832 KB |
Output is correct |