| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 943980 |
2024-03-12T06:02:53 Z |
pcc |
Valley (BOI19_valley) |
C++17 |
|
340 ms |
61008 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const int mxn = 4e5+10;
vector<pii> t1[mxn],t2[mxn];
int w[mxn];
int N,S,Q,E;
pair<pii,int> req[mxn];
bitset<mxn> esc;
ll ans[mxn];
pii eid[mxn];
bitset<mxn> shop;
bool peko(pii r,int p){
return r.fs<=p&&p<=r.sc;
}
namespace ESC{
int pt = 0;
pii eul[mxn];
void dfs(int now,int par){
eul[now].fs = ++pt;
for(auto nxt:t1[now]){
if(nxt.fs == par)continue;
dfs(nxt.fs,now);
}
eul[now].sc = pt;
}
void GO(){
dfs(E,E);
esc.set();
for(int i = 1;i<=Q;i++){
auto [a,b] = req[i].fs;
auto c = req[i].sc;
if(peko(eul[a],eul[c].fs)&&peko(eul[b],eul[c].fs))esc[i] = false;
}
return;
}
}
const ll inf = 1e14;
namespace CD{
bitset<mxn> del;
int sz[mxn];
ll dep[mxn];
pii eul[mxn];
int pt;
vector<array<int,3>> ask[mxn];
pll seg[mxn*4];
void modify(int now,int l,int r,int s,int e,ll v){
if(l>=s&&e>=r){
seg[now].sc += v;
return;
}
int mid = (l+r)>>1;
if(mid>=s)modify(now*2+1,l,mid,s,e,v);
if(mid<e)modify(now*2+2,mid+1,r,s,e,v);
seg[now].fs = min(seg[now*2+1].fs+seg[now*2+1].sc,seg[now*2+2].fs+seg[now*2+2].sc);
return;
}
int szdfs(int now,int par){
sz[now] = 1;
for(auto nxt:t1[now]){
if(nxt.fs == par||del[nxt.fs])continue;
sz[now] += szdfs(nxt.fs,now);
}
return sz[now];
}
int find_centroid(int now,int par,int tar){
for(auto nxt:t1[now]){
if(nxt.fs == par||del[nxt.fs])continue;
if(sz[nxt.fs]>tar)return find_centroid(nxt.fs,now,tar);
}
return now;
}
void dfs(int now,int par){
eul[now].fs = ++pt;
if(shop[now])modify(0,1,N,eul[now].fs,eul[now].fs,dep[now]-inf);
for(auto nxt:t1[now]){
if(nxt.fs == par||del[nxt.fs])continue;
dep[nxt.fs] = dep[now]+nxt.sc;
dfs(nxt.fs,now);
}
eul[now].sc = pt;
return;
}
void dfs1(int now,int par){
for(auto [a,b,id]:ask[now]){
if(peko(eul[a],eul[now].fs)&&peko(eul[b],eul[now].fs))continue;
if(peko(eul[b],eul[a].fs))swap(a,b);
modify(0,1,N,eul[b].fs,eul[b].sc,inf);
ans[id] = min(ans[id],dep[now]+seg[0].fs+seg[0].sc);
modify(0,1,N,eul[b].fs,eul[b].sc,-inf);
}
for(auto nxt:t1[now]){
if(nxt.fs == par||del[nxt.fs])continue;
dfs1(nxt.fs,now);
}
return;
}
void dfs2(int now,int par){
if(shop[now])modify(0,1,N,eul[now].fs,eul[now].fs,-dep[now]+inf);
for(auto nxt:t1[now]){
if(nxt.fs == par||del[nxt.fs])continue;
dfs2(nxt.fs,now);
}
return;
}
void CD(int now){
szdfs(now,now);
now = find_centroid(now,now,(sz[now]-1)/2);
pt = 0;
dep[now] = 0;
dfs(now,now);
dfs1(now,now);
dfs2(now,now);
del[now] = true;
for(auto nxt:t1[now]){
if(del[nxt.fs])continue;
CD(nxt.fs);
}
return;
}
void GO(){
for(int i = 1;i<=N;i++)modify(0,1,N,i,i,inf);
for(int i = 1;i<=Q;i++){
ans[i] = inf;
auto [a,b] = req[i].fs;
auto c = req[i].sc;
ask[c].push_back(array<int,3>({a,b,i}));
}
CD(1);
return;
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N>>S>>Q>>E;
for(int i = 1;i<N;i++){
int a,b,c;
cin>>a>>b>>c;
t1[a].push_back({b,c});
t1[b].push_back({a,c});
eid[i] = {a,b};
}
for(int i = 1;i<=S;i++){
int k;
cin>>k;
shop[k] = true;
}
for(int i = 1;i<=Q;i++){
int id,p;
cin>>id>>p;
req[i] = {eid[id],p};
}
ESC::GO();
CD::GO();
for(int i = 1;i<=Q;i++){
if(esc[i])cout<<"escaped\n";
else if(ans[i]>=inf)cout<<"oo\n";
else cout<<ans[i]<<'\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
44576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
44576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
340 ms |
61008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
44576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
