Submission #16834

---

Source Code Expand

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

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

using namespace std;

struct interval{ int a,b; };

class Fenwick_tree_dual{
	int n,a[200000];

public:
	void build(int n){
		this->n=n;
		rep(i,n) a[i]=0;
	}

	void add(int i,int j,int v){
		if(i==0){
			for(;j>=0;j=(j&(j+1))-1) a[j]+=v;
			return;
		}
		add(0,j,v);
		add(0,i-1,-v);
	}

	int sum(int i){
		int s=0;
		for(;i<n;i|=i+1) s+=a[i];
		return s;
	}
};

struct segment_tree{
	int n,seg[1<<19];

	void build(int N){
		for(n=1;n<N;n*=2);
	}

	int query(int v){
		v+=n;
		int res=seg[v];
		for(;v/=2;) res=max(res,seg[v]);
		return res;
	}

	void update_max(int l,int r,int val,int a,int b,int u){
		if(l<=a && b<=r){ seg[u]=max(seg[u],val); return; }

		int c=(a+b)/2;
		if(l<c && a<r) update_max(l,r,val,a,c,2*u+0);
		if(l<b && c<r) update_max(l,r,val,c,b,2*u+1);
	}

	void update_max(int l,int r,int val){ update_max(l,r+1,val,0,n,1); }
};

int n,par[100000]; // par[u] := ( 頂点 u の親 )
vector<int> G[100000];

int n_ord,inv[200000]; // inv[i] := ( うれしい順序における i 番目はどの頂点か )
interval I[100000]; // I[u] := ( うれしい順序において、頂点 u の部分木に相当する区間 )
Fenwick_tree_dual size; // 各頂点を根とする部分木のサイズ

bool del[100000]; // del[u] := ( 頂点 u が削除されたかどうか )
segment_tree root; // 各頂点が属する木の根

multiset<int> ans;

int dfs(int u,int pre){
	par[u]=pre;
	int tmp=n_ord;
	I[u].a=n_ord;
	inv[n_ord++]=u;

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

	I[u].b=n_ord++;

	size.add(tmp,tmp,sz);
	return sz;
}

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);
	}
	size.build(2*n);
	root.build(2*n);
	dfs(0,-1);
	ans.insert(n);
}

int query(int v){
	int r=inv[root.query(I[v].a)];
	if(v==r){
		// v に対する処理
		int sz=size.sum(I[r].a)-size.sum(I[r].b); // r を部分木とする頂点のサイズ
		ans.erase(ans.find(sz));
	}
	else{
		// v から r へ至るパス上の頂点に対する処理
		int sz1=size.sum(I[r].a)-size.sum(I[r].b);
		int sz2=size.sum(I[v].a)-size.sum(I[v].b);
		ans.erase(ans.find(sz1));
		ans.insert(sz1-sz2);
		size.add(I[r].a,I[v].a,-sz2);
	}

	// v の子孫に対する処理
	rep(i,G[v].size()){
		int u=G[v][i];
		if(u==par[v] || del[u]) continue;
		int sz=size.sum(I[u].a)-size.sum(I[u].b); // u を部分木とする頂点のサイズ
		ans.insert(sz);
		root.update_max(I[u].a,I[u].b,I[u].a);
	}

	del[v]=true;
	return *ans.rbegin();
}

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