Submission #16663

---

Source Code Expand

#include"animals.h"
#include<set>
#include<cstdio>
#include<vector>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int INF=1<<29;

int n,task_type;
vector<int> G[100000];

// subtask 2 用
int perm[100000]; // 頂点を整列する順列
set< pair<int,int> > S1,S2; // S1:[left, right], S2:[-width, left]

void init(int n,int E[][2]){
	::n=n;
	rep(i,n-1){
		int u=E[i][0],v=E[i][1];
		::G[u].push_back(v);
		::G[v].push_back(u);
	}

	if(n<=1000) task_type=1;
	else{
		int deg[3]={};
		rep(u,n){
			int d=G[u].size();
			if(d==1 || d==2) deg[d]++;
		}
		if(deg[1]==2 && deg[2]==n-2){
			task_type=2;
		}
		else{
			task_type=3;
		}
	}

	if(task_type==2){ // 頂点を一列に並べ替える
		int u0;
		rep(u,n) if(G[u].size()==1) u0=u;

		int pre=-1;
		perm[u0]=0;
		rep(t,n-1){
			if(G[u0][0]==pre) u0=G[u0][1];
			else              u0=G[u0][0];
			perm[u0]=t+1;
		}

		static vector<int> G2[100000];
		rep(u,n) rep(i,G[u].size()) G2[perm[u]].push_back(perm[G[u][i]]);
		rep(u,n) G[u]=G2[u];

		S1.insert(make_pair(0,n-1));
		S2.insert(make_pair(-n,0));
	}
}

bool vis[1000];
int dfs(int u,int pre){
	vis[u]=true;

	int res=1;
	rep(i,G[u].size()){
		int v=G[u][i];
		if(v!=pre) res+=dfs(v,u);
	}
	return res;
}

int query_subtask1(int v0){
	G[v0].clear();
	rep(u,n) rep(i,G[u].size()) {
		int v=G[u][i];
		if(v==v0){
			G[u].erase(G[u].begin()+i);
			break;
		}
	}

	rep(u,n) vis[u]=false;
	int res=0;
	rep(u,n) if(!vis[u]) res=max(res,dfs(u,-1));
	return res;
}

int query_subtask2(int v0){
	v0=perm[v0];

	set< pair<int,int> >::iterator it;
	it=--S1.upper_bound(make_pair(v0,INF));

	int l=it->first,r=it->second;
	S1.erase(it);
	S2.erase(make_pair(-(r-l+1),l));
	if(l<v0) S1.insert(make_pair(l,v0-1)), S2.insert(make_pair(-(v0-l),l));
	if(v0<r) S1.insert(make_pair(v0+1,r)), S2.insert(make_pair(-(r-v0),v0+1));

	return -S2.begin()->first;
}

int query(int v0){
	switch(task_type){
		case 1: return query_subtask1(v0);
		case 2: return query_subtask2(v0);
		default: return -1; // very challenging problem!!
	}
}

Submission Info

Compile Error

./grader.cpp: In function ‘int main()’:
./grader.cpp:15: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./grader.cpp:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./grader.cpp:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

Judge Result