Submission #1119238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119238		MrAndria	Tourism (JOI23_tourism)	C++17	28 / 100	5067 ms	23524 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
//#define int long long
int n,k,u,v,tin[200005],m,num[200005],val[200005],l,r,ans[200005],a[200005],sz,timer=0,dst[200005],lg,up[200005][25],tout[200005],q;
pair <pair <int,int> ,int> query[200005];
vector <int> adj[100005];
set <int> s;
void dfs(int x,int p,int ds){
    tin[x]=timer++;
    val[tin[x]]=x;
    dst[x]=ds;
    up[x][0]=p;
    for (int i = 1; i <= lg; ++i)
        up[x][i] = up[up[x][i-1]][i-1];
    for(int u=0;u<adj[x].size();u++){
        if(adj[x][u]!=p){
            dfs(adj[x][u],x,ds+1);

        }
    }
    tout[x] = timer++;
}
bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = lg; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
int dist(int x,int y){
	return dst[x]+dst[y]-2*dst[lca(x,y)];
}
inline void add(int x){
    // cout<<x<<"-"<<tin[x]<<endl;
    num[x]++;
    if(num[x]>1){
        return;
    }
    if(s.size()==0){
        s.insert(tin[x]);
        sz=0;
 
        return;
    }
    s.insert(tin[x]);
    
	set <int> :: iterator it=s.lower_bound(tin[x]);
    set <int> :: iterator it1=it;
    set <int> :: iterator it2=it;
    if(it1==s.begin()){
        it1=s.end();
 
    }
    it1--;
    it2++;
    if(it2==s.end()){
        it2=s.begin();
 
    }
	// cout<<(*it1)<<" "<<(*it)<<" "<<(*it2)<<" "<<val[(*it1)]<<" "<<val[(*it)]<<" "<<val[(*it2)]<<" "<<s.size()<<" "<<dist(val[(*it1)],val[(*it)])<<" "<<dist(val[(*it)],val[(*it2)])<<" "<<dist(val[(*it1)],val[(*it2)])<<" add\n";
    sz+=(dist(val[(*it1)],val[(*it)])+dist(val[(*it)],val[(*it2)])-dist(val[(*it1)],val[(*it2)]));
//    cout<<" "<<sz<<endl;
}
inline void remove(int x){
    num[x]--;
    if(num[x]>0){
        return;
    }
    set <int> :: iterator it=s.lower_bound(tin[x]);
    if(s.size()==1){
        s.erase(it);
//        cout<<s.size()<<endl;
        sz=0;
 
        return;
    }
    set <int> :: iterator it1=it;
    set <int> :: iterator it2=it;
    if(it1==s.begin()){
        it1=s.end();
 
    }
    it1--;
    it2++;
    if(it2==s.end()){
        it2=s.begin();
 
    }
//    cout<<(*it1)<<" "<<(*it)<<" "<<(*it2)<<" "<<val[(*it1)]<<" "<<val[(*it)]<<" "<<val[(*it2)]<<" "<<s.size()<<" "<<dist(val[(*it1)],val[(*it)])<<" "<<dist(val[(*it)],val[(*it2)])<<" "<<dist(val[(*it1)],val[(*it2)])<<" remove";
    sz-=(dist(val[(*it1)],val[(*it)])+dist(val[(*it)],val[(*it2)])-dist(val[(*it1)],val[(*it2)]));
    
    s.erase(it);
    
//    cout<<" "<<sz<<endl;
}
bool comp(pair <pair <int,int>,int> a, pair <pair <int,int> ,int > b){
    if(a.ff.ff/k ==b.ff.ff/k){
        return a.ff.ss<b.ff.ss;
    }
    return (a.ff.ff)/k < (b.ff.ff)/k;
}
int main(){
    scanf("%d%d%d",&n,&m,&q);

    lg=ceil(log2(n));
    k=ceil(sqrt(m));
    
    for(int i=1;i<=n-1;i++){
        scanf("%d%d",&u,&v);
        adj[u].pb(v);
        adj[v].pb(u);

    }
    for(int i=1;i<=m;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=q;i++){
        scanf("%d%d",&query[i].ff.ff,&query[i].ff.ss);
        query[i].ss=i;
        
    }

    dfs(1,1,0);
    sort(query+1,query+q+1,comp);
    int tl=1;
    int tr=1;
    int l,r;
    add(a[tl]);
    for(int i=1;i<=q;i++){
    	l=query[i].ff.ff;
        r=query[i].ff.ss;
        while(tr<r){
            tr++;
            add(a[tr]);

        }
        while(l<tl){
            tl--;
            add(a[tl]);
        }
        while(r<tr){
            remove(a[tr]);
            tr--;
        }

        while(tl<l){
            remove(a[tl]);
            tl++;
        }
        
        ans[query[i].ss]=(sz/2)+1;

    }
    for(int i=1;i<=q;i++){
        printf("%d\n",ans[i]);
    }
}

Compilation message (stderr)

tourism.cpp: In function 'void dfs(int, int, int)':
tourism.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int u=0;u<adj[x].size();u++){
      |                 ~^~~~~~~~~~~~~~
tourism.cpp: In function 'int main()':
tourism.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     scanf("%d%d%d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
tourism.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~
tourism.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
tourism.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         scanf("%d%d",&query[i].ff.ff,&query[i].ff.ss);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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