# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
976392 |
2024-05-06T13:59:55 Z |
ByeWorld |
Valley (BOI19_valley) |
C++14 |
|
378 ms |
69784 KB |
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
const int MAXN = 2e5+10;
const int INF = 1e18+10;
const int LOG = 18;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
int n, s, q, e;
int u[MAXN], v[MAXN], w[MAXN], type[MAXN];
vector <ipii> adj[MAXN];
int par[MAXN], dep[MAXN], in[MAXN], out[MAXN], tim;
int arr[MAXN], chi[MAXN];
void dfs(int nw, int pa){
par[nw] = pa; in[nw] = ++tim; arr[tim] = nw;
dep[nw] = dep[pa]+1;
for(auto ed : adj[nw]){
int nx = ed.fi.fi, idx = ed.se;
if(nx==pa) continue;
chi[idx] = nx;
dfs(nx, nw);
}
out[nw] = ++tim; arr[tim] = -nw;
}
struct fen {
int st[2*MAXN];
void upd(int x, int p){
for(; x<=2*MAXN-20; x+=(x&(-x))) st[x] += p;
}
int que(int x){
int te = 0;
for(; x>=1; x-=(x&(-x))) te += st[x];
return te;
}
} A;
int cpar[MAXN], csiz[MAXN], cdep[MAXN], val[MAXN];
int ans[MAXN], cchi[MAXN], IDX[MAXN], STA[MAXN], dist[MAXN][LOG];
bool rem[MAXN];
vector <int> cari[MAXN];
void pre(int nw, int pa){
csiz[nw] = 1;
for(auto ed : adj[nw]){
int nx = ed.fi.fi;
if(rem[nx] || nx==pa) continue;
pre(nx, nw);
csiz[nw] += csiz[nx];
}
}
int find(int nw){
pre(nw, -1);
bool found = 0; int ret = nw, sta = csiz[nw];
while(!found){
found = 1;
for(auto ed : adj[ret]){
int nx = ed.fi.fi;
if(rem[nx] || csiz[nx] > csiz[ret]) continue;
if(csiz[nx] > sta/2){
found = 0;
ret = nx;
break;
}
}
}
return ret;
}
void DIST(int nw, int par, int wei, int dep){
dist[nw][dep] = wei;
for(auto ed : adj[nw]){
int nx = ed.fi.fi;
if(rem[nx] || nx==par) continue;
DIST(nx, nw, wei+ed.fi.se, dep);
}
}
void build(int nw, int pa, int DEP){
// cout << " masuk\n";
int cen = find(nw);
// cout << cen << " cen\n";
rem[cen] = 1; cdep[cen] = DEP; cpar[cen] = pa;
DIST(cen, -1, 0, cdep[cen]);
for(auto ed : adj[cen]){
int nx = ed.fi.fi;
if(rem[nx]) continue;
build(nx, cen, DEP+1);
}
}
bool vis[MAXN];
void UPD(int nw){
int sta = nw;
for(int i=cdep[sta]; i>=1; i--){
val[nw] = min(val[nw], dist[sta][i]);
nw = cpar[nw];
}
}
int QUE(int nw){
int ret = INF;
int sta = nw;
for(int i=cdep[sta]; i>=1; i--){
if(vis[nw]) ret = min(ret, dist[sta][i]+val[nw]);
nw = cpar[nw];
}
return ret;
}
void ANS(int nw, int par){
for(auto ed : adj[nw]){
int nx = ed.fi.fi;
if(nx == par) continue;
ANS(nx, nw);
}
if(type[nw]) UPD(nw);
vis[nw] = 1;
// cout << nw << " upd\n";
for(auto in : cari[nw]){
int idx = IDX[in], sta = STA[in];
ans[in] = QUE(sta);
// cout << in << ' '<< sta << " idx\n";
}
}
signed main(){
// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> s >> q >> e;
for(int i=1; i<=n-1; i++){
cin >> u[i] >> v[i] >> w[i];
adj[u[i]].pb({{v[i], w[i]}, i});
adj[v[i]].pb({{u[i], w[i]}, i});
}
dfs(e, 0);
for(int i=1; i<=s; i++){
int x; cin >> x;
type[x] = 1;
}
build(e, 0, 1);
// cout << "p\n";
for(int i=1; i<=n; i++){
val[i] = INF;
}
// for(int i=1; i<=n; i++){
// cout << "i"<< i << " \n";
// for(int j=1; j<=3; j++) cout << dist[i][j] << ' ';
// cout << '\n';
// }
for(int i=1; i<=n-1; i++){
if(cdep[u[i]] < cdep[v[i]]) cchi[i] = v[i]; // v di bawah
else cchi[i] = u[i];
}
for(int XX=1; XX<=q; XX++){
int idx, sta; cin >> idx >> sta;
IDX[XX] = idx; STA[XX] = sta;
int node = chi[idx]; // upd child dari edge
A.upd(in[node], 1); A.upd(out[node], -1);
if(A.que(in[sta]) == 0){ // masi bisa ke root
ans[XX] = -1;
// cout << "escaped\n";
} else {
// cari ans nya
// cout << cchi[idx] << ' ' << XX << " xx\n";
cari[cchi[idx]].pb(XX); // dep dr node bawah dr edge idx
}
A.upd(in[node], -1); A.upd(out[node], 1);
}
// sort dr paling bawah
ANS(e, -1);
for(int i=1; i<=q; i++){
if(ans[i] == -1) cout << "escaped\n";
else if(ans[i] >= INF) cout << "oo\n";
else cout << ans[i] << '\n';
}
}
Compilation message
valley.cpp: In function 'void ANS(long long int, long long int)':
valley.cpp:129:7: warning: unused variable 'idx' [-Wunused-variable]
129 | int idx = IDX[in], sta = STA[in];
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
37468 KB |
Output is correct |
2 |
Incorrect |
12 ms |
37468 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
37468 KB |
Output is correct |
2 |
Incorrect |
12 ms |
37468 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
256 ms |
67084 KB |
Output is correct |
2 |
Correct |
293 ms |
67028 KB |
Output is correct |
3 |
Correct |
345 ms |
66896 KB |
Output is correct |
4 |
Correct |
375 ms |
68436 KB |
Output is correct |
5 |
Correct |
345 ms |
67668 KB |
Output is correct |
6 |
Correct |
378 ms |
69784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
37468 KB |
Output is correct |
2 |
Incorrect |
12 ms |
37468 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |