oj.uz

Submission #211070

# Submission time Handle Problem Language Result Execution time Memory
211070 2020-03-19T07:11:33 Z ryansee Balanced Tree (info1cup18_balancedtree) C++14
0 / 100
 4000 ms 171128 KB 
#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 (500006)
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;
	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
	seg[0]=new node(0, 5e5+2, 0);
	seg[1]=new node(0, 5e5+2, 1);
	cin>>t;
	while(t--)solve();
}

Compilation message

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:135:2: note: in expansion of macro 'FOR'
  FOR(i,1,n)cout<<C[i]<<' ';cout<<'\n';
  ^~~
balancedtree.cpp:135: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
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4078 ms 137336 KB Time limit exceeded
2 Execution timed out 4070 ms 137336 KB Time limit exceeded

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4070 ms 137952 KB Time limit exceeded
2 Correct 717 ms 141624 KB Output is correct
3 Correct 843 ms 139284 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4066 ms 137464 KB Time limit exceeded
2 Execution timed out 4048 ms 155768 KB Time limit exceeded
3 Execution timed out 4108 ms 145400 KB Time limit exceeded

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4061 ms 139000 KB Time limit exceeded
2 Execution timed out 4077 ms 137592 KB Time limit exceeded
3 Execution timed out 4051 ms 137944 KB Time limit exceeded
4 Execution timed out 4083 ms 137336 KB Time limit exceeded
5 Execution timed out 4054 ms 137464 KB Time limit exceeded
6 Execution timed out 4083 ms 138232 KB Time limit exceeded
7 Execution timed out 4078 ms 137464 KB Time limit exceeded
8 Execution timed out 4072 ms 137336 KB Time limit exceeded
9 Execution timed out 4072 ms 137464 KB Time limit exceeded

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4078 ms 137336 KB Time limit exceeded
2 Execution timed out 4070 ms 137336 KB Time limit exceeded
3 Execution timed out 4070 ms 137952 KB Time limit exceeded
4 Correct 717 ms 141624 KB Output is correct
5 Correct 843 ms 139284 KB Output is correct
6 Execution timed out 4066 ms 137464 KB Time limit exceeded
7 Execution timed out 4048 ms 155768 KB Time limit exceeded
8 Execution timed out 4108 ms 145400 KB Time limit exceeded
9 Execution timed out 4061 ms 139000 KB Time limit exceeded
10 Execution timed out 4077 ms 137592 KB Time limit exceeded
11 Execution timed out 4051 ms 137944 KB Time limit exceeded
12 Execution timed out 4083 ms 137336 KB Time limit exceeded
13 Execution timed out 4054 ms 137464 KB Time limit exceeded
14 Execution timed out 4083 ms 138232 KB Time limit exceeded
15 Execution timed out 4078 ms 137464 KB Time limit exceeded
16 Execution timed out 4072 ms 137336 KB Time limit exceeded
17 Execution timed out 4072 ms 137464 KB Time limit exceeded
18 Execution timed out 4077 ms 138488 KB Time limit exceeded
19 Execution timed out 4082 ms 144376 KB Time limit exceeded
20 Execution timed out 4072 ms 137336 KB Time limit exceeded
21 Execution timed out 4069 ms 171128 KB Time limit exceeded
22 Execution timed out 4062 ms 137464 KB Time limit exceeded