Submission #3177643


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){
    if(sum(pre[vs[a]],pro[vs[a]],0,(1<<19)-1,0)>=k){
        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());
        for(int i=0;i<w.size();i++)update(w[i]);
        int c;
        for(int i=1;i<w.size();i++){
            c=lca(w[i],w[i-1]);
            update(c);
        }
        for(int i=0;i<w.size();i++){
            add(w[i],-1);
        }
        printf("%d\n",dp[ans]);
        q--;
    }
}

Submission Info

Submission Time
Task F - 根付き木のみさわさん
User nxteru
Language C++14 (GCC 5.4.1)
Score 130
Code Size 2728 Byte
Status AC
Exec Time 170 ms
Memory 25472 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:83:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
./Main.cpp:86: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:97:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
                   ^
./Main.cpp:100: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:104:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a);
                          ...

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 20 / 20 110 / 110
Status
AC × 3
AC × 29
AC × 55
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt
Subtask2 sample_01.txt, sample_02.txt, sample_03.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_15.txt, subtask_02_16.txt, subtask_02_17.txt, subtask_02_18.txt, subtask_02_19.txt, subtask_02_20.txt, subtask_02_21.txt, subtask_02_22.txt, subtask_02_23.txt, subtask_02_24.txt, subtask_02_25.txt, subtask_02_26.txt
Case Name Status Exec Time Memory
sample_01.txt AC 5 ms 12544 KB
sample_02.txt AC 4 ms 12544 KB
sample_03.txt AC 4 ms 12544 KB
subtask_01_01.txt AC 4 ms 12544 KB
subtask_01_02.txt AC 4 ms 12544 KB
subtask_01_03.txt AC 4 ms 12544 KB
subtask_01_04.txt AC 6 ms 12544 KB
subtask_01_05.txt AC 28 ms 12544 KB
subtask_01_06.txt AC 5 ms 12544 KB
subtask_01_07.txt AC 6 ms 12544 KB
subtask_01_08.txt AC 23 ms 12544 KB
subtask_01_09.txt AC 4 ms 12544 KB
subtask_01_10.txt AC 6 ms 12544 KB
subtask_01_11.txt AC 23 ms 12544 KB
subtask_01_12.txt AC 4 ms 12544 KB
subtask_01_13.txt AC 6 ms 12544 KB
subtask_01_14.txt AC 23 ms 12544 KB
subtask_01_15.txt AC 5 ms 12544 KB
subtask_01_16.txt AC 7 ms 12544 KB
subtask_01_17.txt AC 26 ms 12544 KB
subtask_01_18.txt AC 5 ms 12544 KB
subtask_01_19.txt AC 6 ms 12544 KB
subtask_01_20.txt AC 25 ms 12544 KB
subtask_01_21.txt AC 5 ms 12544 KB
subtask_01_22.txt AC 6 ms 12544 KB
subtask_01_23.txt AC 26 ms 12544 KB
subtask_01_24.txt AC 5 ms 12544 KB
subtask_01_25.txt AC 6 ms 12544 KB
subtask_01_26.txt AC 26 ms 12544 KB
subtask_02_01.txt AC 125 ms 17660 KB
subtask_02_02.txt AC 139 ms 17280 KB
subtask_02_03.txt AC 145 ms 17152 KB
subtask_02_04.txt AC 118 ms 18304 KB
subtask_02_05.txt AC 134 ms 17792 KB
subtask_02_06.txt AC 137 ms 17664 KB
subtask_02_07.txt AC 144 ms 21628 KB
subtask_02_08.txt AC 153 ms 21376 KB
subtask_02_09.txt AC 159 ms 21120 KB
subtask_02_10.txt AC 139 ms 18428 KB
subtask_02_11.txt AC 153 ms 17920 KB
subtask_02_12.txt AC 157 ms 17920 KB
subtask_02_13.txt AC 131 ms 17788 KB
subtask_02_14.txt AC 143 ms 17536 KB
subtask_02_15.txt AC 143 ms 17408 KB
subtask_02_16.txt AC 146 ms 25468 KB
subtask_02_17.txt AC 156 ms 25088 KB
subtask_02_18.txt AC 170 ms 24960 KB
subtask_02_19.txt AC 131 ms 17788 KB
subtask_02_20.txt AC 143 ms 17408 KB
subtask_02_21.txt AC 150 ms 17280 KB
subtask_02_22.txt AC 151 ms 22652 KB
subtask_02_23.txt AC 165 ms 24960 KB
subtask_02_24.txt AC 167 ms 21120 KB
subtask_02_25.txt AC 117 ms 17408 KB
subtask_02_26.txt AC 134 ms 25472 KB