Submission #485982


Source Code Expand

Copy
#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;

typedef pair<int,int> P;

int N;
vector<int> G[100100];
int pre[100100],pos[100100];

int par[100100][20];
int dep[100100];

int get_lca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	int d=dep[u]-dep[v];
	for(int i=0;i<20;i++){
		if(((d>>i)&1)==1){
			u=par[u][i];
		}
	}
	if(u==v) return u;
//	printf("(%d %d)\n",u,v);
	for(int i=19;i>=0;i--){
		if(par[u][i]!=par[v][i]){
			u=par[u][i];
			v=par[v][i];
		}
	}
	return par[u][0];
}

int c=1;
void dfs(int v,int p,int d){
//	printf("%d %d %d\n",v,p,d);
	par[v][0]=p;
	pre[v]=c;
	dep[v]=d;
	c++;
	for(int i=0;i<G[v].size();i++){
		int u=G[v][i];
		if(u==p) continue;
		dfs(u,v,d+1);
	}
	pos[v]=c;
}

struct BIT{
	int N;
	int dat[100100];
	void init(int N_){
		N=N_;
		for(int i=0;i<=N;i++) dat[i]=0;
	}
	void add(int i,int x){
		while(i<=N){
			dat[i]+=x;
			i+=(i&(-i));
		}
	}
	int sum(int i){
		int res=0;
		while(i>0){
			res+=dat[i];
			i-=(i&(-i));
		}
		return res;
	}
};

BIT bit;

int M,K;
int vs[100100];

P ps[100100];

vector<int> cands;

int solve(){
	for(int i=0;i<M;i++){
		ps[i]=P(pre[vs[i]],vs[i]);
	}
	sort(ps,ps+M);
	cands.clear();
	for(int i=0;i<M;i++){
		cands.push_back(ps[i].second);
	}
	for(int i=0;i+1<M;i++){
		int u=ps[i].second;
		int v=ps[i+1].second;
		int lca=get_lca(u,v);
		cands.push_back(lca);
	}
	int res=-1;
	for(int i=0;i<cands.size();i++){
		int v=cands[i];
		int cnt=bit.sum(pos[v]-1)-bit.sum(pre[v]-1);
//		printf("%d %d\n",v,cnt);
		if(cnt>=K){
			int cur=dep[v];
			if(res==-1||res<cur) res=cur;
		}
	}
	return res;
}

void input_g(){
	scanf("%d",&N);
	for(int i=0;i<N-1;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		u--;v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
}

void init_g(){
	dfs(0,-1,0);
	for(int j=1;j<20;j++){
		for(int i=0;i<N;i++){
			if(par[i][j-1]==-1) par[i][j]=-1;
			else par[i][j]=par[par[i][j-1]][j-1];
		}
	}
/*	for(int i=0;i<N;i++){
		printf("%d %d %d %d\n",pre[i],pos[i],par[i][0],dep[i]);
	}*/
	bit.init(N);
}

void input_q(){
	scanf("%d%d",&M,&K);
	for(int i=0;i<M;i++) scanf("%d",vs+i);
	for(int i=0;i<M;i++) vs[i]--;
	for(int i=0;i<M;i++){
		bit.add(pre[vs[i]],1);
	}
}

void after_q(){
	for(int i=0;i<M;i++){
		bit.add(pre[vs[i]],-1);
	}
}

int main(){
	input_g();
	init_g();
	int Q;
	scanf("%d",&Q);
	for(int q=0;q<Q;q++){
		input_q();
		int ans=solve();
		printf("%d\n",ans);
		after_q();
	}
	return 0;
}

Submission Info

Submission Time
Task F - 根付き木のみさわさん
User wo01
Language C++ (GCC 4.9.2)
Score 130
Code Size 2586 Byte
Status
Exec Time 225 ms
Memory 24224 KB

Compile Error

./Main.cpp: In function ‘void input_g()’:
./Main.cpp:112:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
                ^
./Main.cpp:115:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
                      ^
./Main.cpp: In function ‘void input_q()’:
./Main.cpp:137:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&M,&K);
                     ^
./Main.cpp:138:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<M;i++) scanf("%d",vs+i);
                                       ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:155:16: warning: ignoring return value of ‘int scanf(const char*,...

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 20 / 20 110 / 110
Status
× 3
× 29
× 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 32 ms 3868 KB
sample_02.txt 31 ms 3876 KB
sample_03.txt 28 ms 3828 KB
subtask_01_01.txt 29 ms 4004 KB
subtask_01_02.txt 29 ms 3872 KB
subtask_01_03.txt 29 ms 3876 KB
subtask_01_04.txt 31 ms 4000 KB
subtask_01_05.txt 47 ms 4000 KB
subtask_01_06.txt 30 ms 4000 KB
subtask_01_07.txt 31 ms 3872 KB
subtask_01_08.txt 46 ms 3872 KB
subtask_01_09.txt 29 ms 3976 KB
subtask_01_10.txt 29 ms 3872 KB
subtask_01_11.txt 43 ms 3880 KB
subtask_01_12.txt 28 ms 3868 KB
subtask_01_13.txt 30 ms 3996 KB
subtask_01_14.txt 46 ms 3968 KB
subtask_01_15.txt 31 ms 3884 KB
subtask_01_16.txt 31 ms 3880 KB
subtask_01_17.txt 45 ms 3872 KB
subtask_01_18.txt 30 ms 3876 KB
subtask_01_19.txt 31 ms 3872 KB
subtask_01_20.txt 44 ms 3996 KB
subtask_01_21.txt 30 ms 4048 KB
subtask_01_22.txt 30 ms 3880 KB
subtask_01_23.txt 47 ms 3876 KB
subtask_01_24.txt 30 ms 4004 KB
subtask_01_25.txt 31 ms 3944 KB
subtask_01_26.txt 42 ms 3876 KB
subtask_02_01.txt 185 ms 17952 KB
subtask_02_02.txt 186 ms 16800 KB
subtask_02_03.txt 193 ms 16676 KB
subtask_02_04.txt 180 ms 18464 KB
subtask_02_05.txt 179 ms 17308 KB
subtask_02_06.txt 182 ms 17056 KB
subtask_02_07.txt 184 ms 21016 KB
subtask_02_08.txt 185 ms 20268 KB
subtask_02_09.txt 192 ms 19748 KB
subtask_02_10.txt 182 ms 18580 KB
subtask_02_11.txt 188 ms 17256 KB
subtask_02_12.txt 185 ms 17184 KB
subtask_02_13.txt 212 ms 18088 KB
subtask_02_14.txt 205 ms 17316 KB
subtask_02_15.txt 210 ms 16932 KB
subtask_02_16.txt 197 ms 24224 KB
subtask_02_17.txt 196 ms 23068 KB
subtask_02_18.txt 199 ms 22688 KB
subtask_02_19.txt 208 ms 18080 KB
subtask_02_20.txt 206 ms 16932 KB
subtask_02_21.txt 206 ms 16672 KB
subtask_02_22.txt 218 ms 21908 KB
subtask_02_23.txt 225 ms 23184 KB
subtask_02_24.txt 224 ms 19748 KB
subtask_02_25.txt 205 ms 16548 KB
subtask_02_26.txt 213 ms 22564 KB