# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
764196 |
2023-06-23T08:31:46 Z |
huutuan |
Tourism (JOI23_tourism) |
C++14 |
|
60 ms |
32432 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)
const int N=1e5+1, S=320, LG=17;
struct query{
int l, r, i;
query(int a=0, int b=0, int c=0): l(a), r(b), i(c){}
bool operator<(const query& x){
return l/S!=x.l/S?l<x.l:r<x.r;
}
} qq[N];
int n, m, q, a[N], tdfs, tin[N], tout[N], up[N][LG], dep[N], ans[N];
vector<int> g[N];
void dfs(int u){
tin[u]=++tdfs;
dep[u]=dep[up[u][0]]+1;
for (int v:g[u]) if (v!=up[u][0]){
up[v][0]=u;
for (int k=1; k<LG; ++k) up[v][k]=up[up[v][k-1]][k-1];
dfs(v);
}
tout[u]=tdfs;
}
int lca(int u, int v){
if (dep[u]!=dep[v]){
if (dep[u]<dep[v]) swap(u, v);
int d=dep[u]-dep[v];
for (int k=0; k<LG; ++k) if (d>>k&1) u=up[u][k];
}
if (u==v) return u;
for (int k=LG-1; k>=0; --k) if (up[u][k]!=up[v][k]) u=up[u][k], v=up[v][k];
return up[u][0];
}
void solve(int tc){
// cout << "Case #" << tc << ": ";
cin >> n >> m >> q;
for (int i=1; i<n; ++i){
int x, y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1);
for (int i=1; i<=m; ++i) cin >> a[i];
for (int i=1; i<=q; ++i){
int x, y; cin >> x >> y;
qq[i]={x, y, i};
}
sort(qq+1, qq+q+1);
set<pair<int, int>> st;
int val=0;
function<int(int, int)> calc=[&](int x, int y) -> int {
return dep[y]-dep[lca(x, y)];
};
function<void(int)> add=[&](int x) -> void {
if (st.empty()){
st.emplace(tin[x], x);
return;
}
auto it=st.lower_bound({tin[x], x});
auto previt=it==st.begin()?prev(st.end()):prev(it);
auto nextit=it==st.end()?st.begin():it;
val-=calc(previt->second, nextit->second);
val+=calc(previt->second, x);
val+=calc(x, nextit->second);
st.emplace(tin[x], x);
};
function<void(int)> del=[&](int x) -> void {
if (sz(st)==1){
st.erase({tin[x], x});
return;
}
auto it=st.find({tin[x], x});
auto previt=it==st.begin()?prev(st.end()):prev(it);
auto nextit=it==prev(st.end())?st.begin():next(it);
val+=calc(previt->second, nextit->second);
val-=calc(previt->second, x);
val-=calc(x, nextit->second);
st.erase(it);
};
int cl=1, cr=0;
for (int i=1; i<=q; ++i){
int l=qq[i].l, r=qq[i].r;
while (l<cl){
--cl;
add(a[cl]);
}
while (l>cl){
del(a[cl]);
++cl;
}
while (r>cr){
++cr;
add(a[cr]);
}
while (r<cr){
del(a[cr]);
--cr;
}
ans[qq[i].i]=val;
}
for (int i=1; i<=q; ++i) cout << ans[i]+1 << '\n';
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int ntests=1;
// cin >> ntests;
for (int i=1; i<=ntests; ++i) solve(i);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
5028 KB |
Output is correct |
4 |
Runtime error |
9 ms |
10036 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
5028 KB |
Output is correct |
4 |
Runtime error |
9 ms |
10036 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Runtime error |
7 ms |
9940 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Runtime error |
60 ms |
32432 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Runtime error |
7 ms |
9940 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
5028 KB |
Output is correct |
4 |
Runtime error |
9 ms |
10036 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |