Submission #1000008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000008		NintsiChkhaidze	Tourism (JOI23_tourism)	C++17	10 / 100	5063 ms	88552 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;
vector <pii> qr[N];

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 addseg(int l,int r,int col){
    for (int i = l; i <= r; i++)
        arr[i] = col;
}

int get(int x){
    int cnt=0;
    for (int i = 1; i <= n; i++)
        cnt += (arr[i] >= x);
    return cnt;
}

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:68:9: warning: unused variable 'c' [-Wunused-variable]
   68 |     int c = lca(x,y),cnt=0;
      |         ^
tourism.cpp:68:22: warning: unused variable 'cnt' [-Wunused-variable]
   68 |     int c = lca(x,y),cnt=0;
      |                      ^~~

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