Submission #211072

#	Time	Username	Problem	Language	Result	Execution time	Memory
211072		ryansee	Balanced Tree (info1cup18_balancedtree)	C++14	23 / 100	4096 ms	44932 KiB

balancedtree

#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (100006)
ll t,n;
int st[MAXN],en[MAXN],co,depth[MAXN],C[MAXN],bck[MAXN];
vector<int>v[MAXN],dk;
struct node {
	int s,e,m,b;
	ll v,add;
	node*l,*r;
	node(int S,int E,ll bb){
		s=S,e=E,m=(s+e)>>1;
		v=0,add=0,b=bb;
		if(s^e)l=new node(s,m,bb),r=new node(m+1,e,bb);
	}
	void update(int x,int y,ll nval){
		value();
		if(s==x&&e==y){add+=nval;return;}
		if(x>m)r->update(x,y,nval);
		else if(y<=m)l->update(x,y,nval);
		else l->update(x,m,nval),r->update(m+1,y,nval);
		v=min(l->value(),r->value());
	}
	ll value(){
		v+=add;
		if(s^e){
			l->add+=add;
			r->add+=add;
		}
		add=0;
		return v;
	}
	ll rmq(int x,int y){
		if(x>y)return LLINF;
		value();
		if(s==x&&e==y)return v;
		if(x>m)return r->rmq(x,y);
		else if(y<=m)return l->rmq(x,y);
		else return min(l->rmq(x,m),r->rmq(m+1,y));
	}
	void reset(){
		v=add=0;
		if(s^e)l->reset(),r->reset(),v=min(l->v,r->v);
		else v=((s<=n-1&&(C[bck[s]]==b))?depth[bck[s]]:LLINF);
	}
	void pt(){
		// cerr<<s<<' '<<e<<' '<<v<<' '<<bck[s]<<' '<<b<<'\n';
		// if(s^e) l->pt(),r->pt();
	}
} *seg[2];
void dfs(int x,int p){
	bck[co]=x, st[x]=co++;
	for(auto i:v[x])if(i^p){
		depth[i]=depth[x]+1, dfs(i,x);
	}
	en[x]=co-1;
}
ll mx;
void check(int x,int p){
	mx=max(mx,min(seg[C[x]]->rmq(0,st[x]-1),seg[C[x]]->rmq(st[x]+1,n-1)));
	for(auto i:v[x])if(i^p){
		FOR(j,0,1) seg[j]->update(0,co-1,1),seg[j]->update(st[i],en[i],-2);
		check(i,x);
		FOR(j,0,1) seg[j]->update(0,co-1,-1),seg[j]->update(st[i],en[i],2);
	}
}
ll get_ans() {
	FOR(i,1,n)assert(C[i]!=-1);
	seg[0]->reset(),seg[1]->reset();
	mx=0;
	check(1,1);
	return mx;
}
void st1() {
	ll ans=n+1, bruh=0;
	FOR(i,0,(1<<siz(dk))-1){
		FOR(j,0,siz(dk)-1){
			C[dk[j]]=bool((1<<j)&i);
		}
		ll en=get_ans();
		if(en<ans)bruh=i;
		ans=min(ans, en);
	}
	cout<<(ans>=n+1?-1:ans)<<'\n';
	if(ans>=n+1)return;
	FOR(j,0,siz(dk)-1){
		C[dk[j]]=bool((1<<j)&bruh);
	}
	FOR(j,1,n)cout<<C[j]<<' ';cout<<'\n';
}
void solve(){  
	cin>>n;
	FOR(i,0,n)v[i].clear();
	dk.clear();
	FOR(i,0,n)st[i]=en[i]=co=depth[i]=C[i]=bck[i]=0;
	seg[0]=new node(0, n-1, 0), seg[1]=new node(0, n-1, 1);
	FOR(i,0,n-2){
		ll a,b;cin>>a>>b;
		v[a].eb(b),v[b].eb(a);
	}
	FOR(i,1,n){cin>>C[i];if(C[i]==-1)dk.pb(i);}
	dfs(1,1);
	if(*min_element(C+1,C+n+1)==-1){
		st1();
		return;
	}
	ll en=get_ans();
	cout<<(en>=n+1 ? -1 : en)<<'\n';
	if(en>=n+1)return;
	FOR(i,1,n)cout<<C[i]<<' ';cout<<'\n';
}
int main(){
	FAST
	cin>>t;
	while(t--)solve();
}

Compilation message (stderr)

balancedtree.cpp: In function 'void st1()':
balancedtree.cpp:23:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
                    ^
balancedtree.cpp:115:2: note: in expansion of macro 'FOR'
  FOR(j,1,n)cout<<C[j]<<' ';cout<<'\n';
  ^~~
balancedtree.cpp:115:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  FOR(j,1,n)cout<<C[j]<<' ';cout<<'\n';
                            ^~~~
balancedtree.cpp: In function 'void solve()':
balancedtree.cpp:23:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
                    ^
balancedtree.cpp:136:2: note: in expansion of macro 'FOR'
  FOR(i,1,n)cout<<C[i]<<' ';cout<<'\n';
  ^~~
balancedtree.cpp:136:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  FOR(i,1,n)cout<<C[i]<<' ';cout<<'\n';
                            ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 0 / 26
• Subtask 4: 0 / 45
• Subtask 5: 0 / 6