oj.uz

답안 #793290

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
793290 2023-07-25T17:24:25 Z winter0101 Tourism (JOI23_tourism) C++14
0 / 100
 127 ms 17188 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_back
const int maxn=1e5+9;
vector<int>a[maxn];
int sub[maxn];
int dep[maxn];
int p[maxn];
void dfs(int u,int par){
sub[u]=1;
for (auto &v:a[u]){
    if (v==par)continue;
    dep[v]=dep[u]+1;
    p[v]=u;
    dfs(v,u);
    sub[u]+=sub[v];
    if (a[u][0]==par||sub[a[u][0]]<sub[v])swap(v,a[u][0]);
}
}
int pos[maxn],h[maxn],b[maxn];
int tme=0,gr=1;
void hld(int u,int par,int head){
h[u]=head;
pos[u]=++tme;
b[u]=gr;
if (a[u].empty())return;
if (a[u][0]!=par){
    hld(a[u][0],u,head);
}
for (auto v:a[u]){
    if (v==par||v==a[u][0])continue;
    gr++;
    hld(v,u,v);
}
}
int bit[maxn];
int n,m,q;
void add(int ps,int val){
if (ps==0)return;
for(;ps<=n;ps+=(ps-(ps&(ps-1))))bit[ps]+=val;
}
int get(int ps){
int sum=0;
for(;ps>=1;ps-=(ps-(ps&(ps-1))))sum+=bit[ps];
return sum;
}
int get(int l,int r){
return get(r)-get(l-1);
}
struct tim{
int l,r,w;
bool operator < (const tim &p1)const {
return l<p1.l;
}
};
multiset<tim>line[maxn];
multiset<tim>::iterator it;
void update(int u,int v,int w){
while (h[u]!=h[v]){
    if (dep[h[u]]<dep[h[v]])swap(u,v);
    //cout<<u<<" "<<v<<'\n';
    tim tmp={pos[h[u]],pos[u],w};
    int id=b[u];
    while (!line[id].empty()){
        it=line[id].begin();
        auto temp=(*it);
        if (temp.l>tmp.r)break;
        add(temp.w,-(temp.r-temp.l+1));
        if (temp.r<=tmp.r){
        line[id].erase(it);
        }
        else {
        line[id].erase(it);
        temp.l=tmp.r+1;
        line[id].insert(temp);
        add(temp.w,temp.r-tmp.r);
        }
    }
    add(tmp.w,tmp.r-tmp.l+1);
    line[id].insert(tmp);
    u=p[h[u]];
}
if (pos[u]>pos[v])swap(u,v);
tim tmp={pos[u],pos[v],w};
//cerr<<u<<" "<<v<<'\n';
//cerr<<pos[u]<<" "<<pos[v]<<'\n';
//if (w==5)cerr<<pos[u]<<" "<<pos[v]<<'\n';
int id=b[u];
while (!line[id].empty()){
    it=line[id].upper_bound(tmp);
    if (it==line[id].begin())break;
    //cerr<<"haha"<<'\n';
    it--;
    auto temp=(*it);
    if (temp.r<tmp.l)break;
    add(temp.w,-(temp.r-temp.l+1));
    line[id].erase(it);
    if (temp.r>tmp.r){
    tim t1={tmp.r+1,temp.r,temp.w};
    add(temp.w,temp.r-tmp.r);
    temp.r=tmp.r;
    line[id].insert(t1);
    }
    if (temp.l<tmp.l){
    temp.r=tmp.l-1;
    add(temp.w,temp.r-temp.l+1);
    line[id].insert(temp);
    }
}
while (!line[id].empty()){
    it=line[id].lower_bound(tmp);
    if (it==line[id].end())break;
    auto temp=(*it);
    //cerr<<temp.l<<" "<<temp.r<<'\n';
    if (temp.l>tmp.r)break;
    add(temp.w,-(temp.r-temp.l+1));
    line[id].erase(it);
    if (temp.r<=tmp.r)continue;
    temp.l=tmp.r+1;
    add(temp.w,temp.r-temp.l+1);
    line[id].insert(temp);
}
add(tmp.w,tmp.r-tmp.l+1);
line[id].insert(tmp);
}
int city[maxn];
vector<pii>query[maxn];
int ans[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>m>>q;
    for1(i,1,n-1){
    int u,v;
    cin>>u>>v;
    a[u].pb(v);
    a[v].pb(u);
    }
    dfs(1,0);
    hld(1,0,1);
    for1(i,1,m)cin>>city[i];
    for1(i,1,q){
    int l,r;
    cin>>l>>r;
    if (l==r){
        ans[i]=1;
        //cerr<<"xxx";
    }
    else {
        query[r].pb({l,i});
    }
    }
    for1(i,2,m){
    update(city[i],city[i-1],i-1);
    for (auto v:query[i]){
        ans[v.se]=get(v.fi,i);
    }
    }
    //for1(i,1,n)cout<<pos[i]<<'\n';
    //for (auto v:line[1])cout<<v.l<<" "<<v.r<<'\n';
    /*for1(i,1,m){
    cout<<i<<" "<<get(i,i)<<'\n';
    }*/
    //update(4,5,4);
    //update(5,1,5);
    //for1(i,1,n)cout<<i<<" "<<pos[i]<<'\n';
    //for (auto v:line[2])cout<<v.l<<" "<<v.r<<'\n';
    for1(i,1,q)cout<<ans[i]<<'\n';
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Incorrect 5 ms 9684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Incorrect 5 ms 9684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9736 KB Output is correct
2 Incorrect 4 ms 9728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9736 KB Output is correct
2 Correct 95 ms 16168 KB Output is correct
3 Incorrect 127 ms 17188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9656 KB Output is correct
2 Incorrect 5 ms 9684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Incorrect 5 ms 9684 KB Output isn't correct
5 Halted 0 ms 0 KB -