oj.uz

답안 #211072

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
211072 2020-03-19T07:13:00 Z ryansee Balanced Tree (info1cup18_balancedtree) C++14
23 / 100
 4000 ms 44932 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 (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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 3960 KB Output is correct
2 Correct 66 ms 4728 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 28408 KB Output is correct
2 Correct 338 ms 30712 KB Output is correct
3 Correct 274 ms 28536 KB Output is correct

Subtask #3
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4081 ms 2944 KB Time limit exceeded
2 Execution timed out 4066 ms 44932 KB Time limit exceeded
3 Execution timed out 4058 ms 22520 KB Time limit exceeded

Subtask #4
0.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4062 ms 8952 KB Time limit exceeded
2 Execution timed out 4070 ms 3072 KB Time limit exceeded
3 Execution timed out 4067 ms 6008 KB Time limit exceeded
4 Execution timed out 4096 ms 2816 KB Time limit exceeded
5 Execution timed out 4096 ms 3072 KB Time limit exceeded
6 Execution timed out 4050 ms 8184 KB Time limit exceeded
7 Execution timed out 4086 ms 3328 KB Time limit exceeded
8 Execution timed out 4077 ms 2824 KB Time limit exceeded
9 Execution timed out 4059 ms 3072 KB Time limit exceeded

Subtask #5
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 3960 KB Output is correct
2 Correct 66 ms 4728 KB Output is correct
3 Correct 165 ms 28408 KB Output is correct
4 Correct 338 ms 30712 KB Output is correct
5 Correct 274 ms 28536 KB Output is correct
6 Execution timed out 4081 ms 2944 KB Time limit exceeded
7 Execution timed out 4066 ms 44932 KB Time limit exceeded
8 Execution timed out 4058 ms 22520 KB Time limit exceeded
9 Execution timed out 4062 ms 8952 KB Time limit exceeded
10 Execution timed out 4070 ms 3072 KB Time limit exceeded
11 Execution timed out 4067 ms 6008 KB Time limit exceeded
12 Execution timed out 4096 ms 2816 KB Time limit exceeded
13 Execution timed out 4096 ms 3072 KB Time limit exceeded
14 Execution timed out 4050 ms 8184 KB Time limit exceeded
15 Execution timed out 4086 ms 3328 KB Time limit exceeded
16 Execution timed out 4077 ms 2824 KB Time limit exceeded
17 Execution timed out 4059 ms 3072 KB Time limit exceeded
18 Execution timed out 4093 ms 5888 KB Time limit exceeded
19 Execution timed out 4081 ms 33144 KB Time limit exceeded
20 Execution timed out 4062 ms 3076 KB Time limit exceeded
21 Runtime error 14 ms 9216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Execution timed out 4075 ms 2944 KB Time limit exceeded