Submission #1000018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000018		NintsiChkhaidze	Tourism (JOI23_tourism)	C++17	100 / 100	832 ms	79528 KiB

tourism

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define s second
#define f first
#define pii pair <int,int>
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
#define int ll
using namespace std;

const int N = 3e5 + 5;
vector <int> v[N];
int ans[N],ord[N],sz[N],heavy[N],head[N],tin[N];
int timer,d[25][N],dep[N],arr[N],n,m,fen[N];
vector <pii> qr[N];
set <pair<pii,int> > st;

void dfs(int x,int par){
    d[0][x] = par;
    dep[x] = dep[par] + 1;
    sz[x] = 1;

    for (int to: v[x]){
        if (to == par) continue;
        dfs(to,x);
        sz[x] += sz[to];    
        if (sz[to] > sz[heavy[x]]) heavy[x] = to;
    }
}

int lca(int x,int y){
    if (dep[x] < dep[y]) swap(x,y);
    for (int i = 20; i >= 0; i--)
        if (dep[d[i][x]] >= dep[y]) x = d[i][x];

    if (x == y) return x;
    for (int i = 20; i >= 0; i--)
        if (d[i][x] != d[i][y]) 
            x = d[i][x],y = d[i][y];
    
    return d[0][x];
} 
void dfs2(int x,int par,int h){
    tin[x] = ++timer;
    head[x] = h;
    if (heavy[x]) dfs2(heavy[x],x,h);

    for (int to: v[x]){
        if (to == par || to == heavy[x]) continue;
        dfs2(to,x,to);
    }
}

void upd(int idx,int s){
    if (!idx) return;
    while (idx <= 100000){
        fen[idx] += s;
        idx += (idx & (-idx));
    }
}

void addseg(int l,int r,int col){
    upd(col,(r - l + 1));

    set <pair<pii,int> > :: iterator it = st.lower_bound({{l,0},0});
    while (it != st.end()){
        int R = (it -> f).s,L = (it -> f).f,c = (it->s);
        if (l <= L && R <= r) {
            upd(c,-(R - L + 1));
            st.erase(it++);
        } else break;
    }

    st.lower_bound({{l,0},0});
    int R = (it -> f).s,L = (it -> f).f,c = (it->s);
    if (L >= l && L <= r && R >= r) {
        upd(c, -(R - L + 1));
        st.erase(it);

        L = r + 1;
        if (L <= R) upd(c, R - L + 1),st.insert({{L,R},c});
    }

    st.insert({{l,r},col});
    it = st.find({{l,r},col});
    if (it != st.begin()){
        --it;
        int R = (it -> f).s,L = (it -> f).f,c = (it->s);
        if (L <= l && r <= R){
            upd(c, -(r - l + 1));
            st.erase(it);
            
            int rr = l - 1;
            if (L <= rr) st.insert({{L,rr},c});
            int l1 = r + 1;
            if (l1 <= R) st.insert({{l1,R},c});
        }
    }

    it = st.find({{l,r},col});
    if (it != st.begin()){
        --it;
        int R = (it -> f).s,L = (it -> f).f,c = (it->s);
        if (L <= l && R >= l && R <= r){
            int cm = (R - l + 1);
            upd(c,-cm);

            st.erase(it);
            int rr = l - 1;
            if (L <= rr) st.insert({{L,rr},c});
        }
    }
}

int gett(int x){
    int s=0;
    while (x>0){
        s+=fen[x];
        x-=(x&(-x));
    }
    return s;
}

int get(int x){
    return gett(m) - gett(x - 1);
}

void upd(int x,int y,int col){
    int c = lca(x,y),cnt=0;
    while (head[x] != head[y]){
        if (dep[head[x]] < dep[head[y]]) swap(x,y);
        addseg(tin[head[x]],tin[x],col);
        x = d[0][head[x]];
    }
    if (dep[x] < dep[y]) swap(x,y);
    addseg(tin[y],tin[x],col);
}

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

    int q;
    cin>>n>>m>>q;

    for (int i = 1; i < n; i++){
        int a,b;
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }

    dfs(1,1);
    dfs2(1,1,1);
    for (int i=1;i<=20;i++)
        for (int j=1;j<=n;j++)
            d[i][j] = d[i - 1][d[i - 1][j]];
        
    for (int i = 1; i <= m; i++){
        cin >> ord[i];
    }

    for (int i = 1; i <= q; i++){
        int l,r;
        cin>>l>>r;
        qr[r].pb({l,i});
    }

    for (int i = 1; i <= m; i++){
        if (i > 1) upd(ord[i - 1],ord[i],i-1);
        upd(ord[i],ord[i],i);

        for (auto [x,id]: qr[i]){
            ans[id] = get(x);
        }
    }

    for (int i = 1; i <= q; i++)
        cout<<ans[i]<<endl;
}

Compilation message (stderr)

tourism.cpp: In function 'void upd(long long int, long long int, long long int)':
tourism.cpp:130:9: warning: unused variable 'c' [-Wunused-variable]
  130 |     int c = lca(x,y),cnt=0;
      |         ^
tourism.cpp:130:22: warning: unused variable 'cnt' [-Wunused-variable]
  130 |     int c = lca(x,y),cnt=0;
      |                      ^~~

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