Submission #3177623

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
int n,k,K,q,m,dp[200005],vs[200005],pre[200005],pro[200005],seg[1<<20],sg[1<<20],ans;
vector<int>g[100005];
vector<int>w;
int rmin(int a,int b){
    if(dp[a]<dp[b])return a;
    else return b;
}
int rmax(int a,int b){
    if(dp[a]>dp[b])return a;
    else return b;
}
void dfs(int v,int p,int d){
    pro[v]=k;
    pre[v]=k;
    dp[k]=d;
    vs[k++]=v;
    for(int i=0;i<g[v].size();i++){
        int u=g[v][i];
        if(u!=p){
            dfs(u,v,d+1);
            pro[v]=k;
            dp[k]=d;
            vs[k++]=v;
        }
    }
}
void add(int a,int x){
    a+=(1<<19)-1;
    seg[a]+=x;
    while(a>0){
        a=(a-1)/2;
        seg[a]=(seg[a*2+1]+seg[a*2+2]);
    }
}
int sum(int a,int b,int l,int r,int o){
    if(r<a||b<l)return 0;
    if(a<=l&&r<=b)return seg[o];
    return sum(a,b,l,(l+r-1)/2,o*2+1)+sum(a,b,(l+r+1)/2,r,o*2+2);
}
void up(int a,int x){
    a+=(1<<19)-1;
    sg[a]=rmin(sg[a],x);
    while(a>0){
        a=(a-1)/2;
        sg[a]=rmin(sg[a*2+1],sg[a*2+2]);
    }
}
int que(int a,int b,int l,int r,int o){
    if(r<a||b<l)return K;
    if(a<=l&&r<=b)return sg[o];
    return rmin(que(a,b,l,(l+r-1)/2,o*2+1),que(a,b,(l+r+1)/2,r,o*2+2));
}
int lca(int a,int b){
    if(b<a)swap(a,b);
    return que(a,b,0,(1<<19)-1,0);
}
void update(int a){
    a=vs[a];
    ans=rmax(ans,a);
}
int main(void){
    scanf("%d",&n);
    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        g[--a].PB(--b);
        g[b].PB(a);
    }
    dfs(0,-1,0);
    dp[k]=n;
    K=k;
    for(int i=0;i<1<<20;i++)sg[i]=k;
    for(int i=0;i<K;i++){
        up(i,i);
    }
    scanf("%d",&q);
    while(q){
        ans=0;
        scanf("%d%d",&m,&k);
        w.clear();
        for(int i=0;i<m;i++){
            int a;
            scanf("%d",&a);
            a--;
            w.PB(pre[a]);
            add(pre[a],1);
        }
        sort(w.begin(),w.end());
        int c;
        for(int i=0;i+k-1<w.size();i++){
            c=lca(w[i],w[i+k-1]);
            update(c);
        }
        for(int i=0;i<w.size();i++){
            add(w[i],-1);
        }
        printf("%d\n",dp[ans]);
        q--;
    }
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:82:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
./Main.cpp:85:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
                            ^
./Main.cpp:96:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
                   ^
./Main.cpp:99:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&m,&k);
                            ^
./Main.cpp:103:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a);
                           ...

Judge Result