Submission #793340

#	Time	Username	Problem	Language	Result	Execution time	Memory
793340		winter0101	Tourism (JOI23_tourism)	C++14	100 / 100	262 ms	29644 KiB

tourism

#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<=m;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;
    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,q)cout<<ans[i]<<'\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41