oj.uz

답안 #154315

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
154315 2019-09-20T12:44:04 Z ryansee Unique Cities (JOI19_ho_t5) C++14
32 / 100
 1000 ms 65144 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)
#define btinpct(x) __builtin_popcountll((x))
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 to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){if(a>b)swap(a,b);if(a==0)return b;return gcd(b%a,a);}

#define ll /*long long*/ int 
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (200006)
ll n, m;
vector<int> v[MAXN];
int A[MAXN], p[MAXN];
bool F[MAXN];
ll fdist[MAXN], depth[MAXN], rdist[MAXN];
void init(ll x,ll par) {
	rdist[x] = fdist[x] = depth[x]; p[x]=par;
	pi mx=pi(depth[x], 1);
	pi fmx=pi(depth[x], 1);
	for(auto i:v[x]) if(i^par) {
		depth[i]=depth[x]+1; init(i, x);
		rdist[x]=max(rdist[x], rdist[i]);
		if(rdist[i] > mx.f) mx.f=rdist[i], mx.s=1;
		else if(rdist[i] == mx.f) ++ mx.s;
		// fmx=max(fmx, fdist[i]);
		if(fdist[i] > fmx.f) fmx.f=fdist[i], fmx.s=1;
		else if(fdist[i] == fmx.f) ++ fmx.s;
	}
	ll rmx=-1;
	for(auto i:v[x]) if(i^par) {
		if(fdist[i] ^ fmx.f) rmx=max(rmx, rdist[i]);
	}
	if(mx.s == 1 && fmx.f > rmx && fmx.s==1) fdist[x]=fmx.f;
}
ll ans[MAXN];
bool can(set<pi,greater<pi>> s) {
	if(s.empty()) return 1;
	ll x = s.begin()->f;
	ll times=1;
	s.erase(s.begin());
	for(auto i:s) {
		if(i.f == x) ++ times;
	}
	return times==1;
}
void dfs(ll x,ll par,ll dist,ll rup) {
	pi mx = pi(dist , 1);
	ll rmx=0;
	for(auto i:v[x]) if(i^par) {
		fdist[i] -= depth[x];
		if(fdist[i] > mx.f) mx.f = fdist[i], mx.s=1;
		else if(fdist[i] == mx.f) ++ mx.s;
		fdist[i] += depth[x];
		rmx=max(rmx, rdist[i]-depth[x]);
	}
	if(mx.f != dist) rmx=rup; else rmx=0;
	for(auto i:v[x]) if(i^par) if(mx.f != fdist[i]-depth[x]) rmx=max(rmx, rdist[i]-depth[x]);
	// if(x==3) cerr<<mx.f<<' '<<mx.s<<' '<<rmx<<' '<<dist<<' '<<rup<<"\n";
	if(mx.s == 1 && mx.f > rmx) {
		ans[x] = 1;
	}
	set<pi,greater<pi>> ms;
	multiset<ll,greater<ll>> R;
	ms.ins(pi(dist, x)); R.ins(rup);
	for(auto i:v[x]) if(i^par) {
		ms.ins(pi(fdist[i]-depth[x], i));
		R.ins(rdist[i]-depth[x]);
	}
	// while(ms.size() > 4) ms.erase(--ms.end());
	// while(R.size() > 4) R.erase(--R.end());
	ll o=ms.size(); ll oR=R.size();
	for(auto i:v[x])if(i^par){
		ms.erase(pi(fdist[i]-depth[x], i));
		if(ms.begin()->s != x) R.erase(R.find(rdist[ms.begin()->s]-depth[x])); else R.erase(R.find(rup));
		if(*R.begin() == rdist[i]-depth[x]) R.erase(R.begin());
		if((ms.size() >= 2 && ms.begin()->f == next(ms.begin())->f) || (R.size()&&ms.begin()->f <= *R.begin())) {
			if(ms.begin()->s != x) R.ins(rdist[ms.begin()->s]-depth[x]);
			else R.ins(rup);
			dfs(i, x, 1, *R.begin() + 1);
		} else {
			if(ms.begin()->s != x) R.ins(rdist[ms.begin()->s]-depth[x]);
			else R.ins(rup);
			dfs(i, x, (ms.begin()->f) + 1, *R.begin() + 1);
		}
		if(siz(ms) ^ o) ms.ins(pi(fdist[i]-depth[x],i));
		if(siz(R) ^ oR) R.ins(rdist[i]-depth[x]);
	}
}
void comp(ll i) {
	for(auto j:v[i]) if(j^p[i]) comp(j);
	pi ans=pi(0, 1);
	bool gg=0;
	for(auto j:v[i]) if(j^p[i]) { gg |= (!F[j]);
		if(fdist[j] > ans.f) ans.f=fdist[j], ans.s=1;
		else if(fdist[j]==ans.f) ++ ans.s;
	} 
	F[i] = (ans.s == 1);
	if(gg) F[i]=0;
}
int main()
{
	FAST
	cin>>n>>m;
	FOR(i,0,n-2) {
		ll a, b; cin>>a>>b;
		v[a].eb(b), v[b].eb(a);
	}
	FOR(i,1,n) cin>>A[i];
	init(1, 1);
	// comp(1);
	FOR(i,1,n) {
		// cerr<<i<<": "<<fdist[i]<<"\n";
	}
	dfs(1, 1, 0, 0);
	FOR(i,1,n) cout<<ans[i]<<"\n";
}
/*
10 10
2 6
5 8
10 8
1 4
10 6
4 5
10 7
6 9
3 7
1 2 3 4 5 6 7 8 9 10
*/

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Incorrect 9 ms 5240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 285 ms 13308 KB Output is correct
2 Correct 269 ms 43472 KB Output is correct
3 Correct 50 ms 10616 KB Output is correct
4 Correct 394 ms 19644 KB Output is correct
5 Correct 580 ms 53524 KB Output is correct
6 Correct 479 ms 48376 KB Output is correct
7 Correct 499 ms 23024 KB Output is correct
8 Correct 436 ms 26052 KB Output is correct
9 Correct 418 ms 25484 KB Output is correct
10 Correct 434 ms 25808 KB Output is correct
11 Correct 1000 ms 37700 KB Output is correct
12 Correct 477 ms 65144 KB Output is correct
13 Correct 611 ms 43344 KB Output is correct
14 Correct 508 ms 47220 KB Output is correct
15 Correct 973 ms 38872 KB Output is correct
16 Correct 612 ms 47860 KB Output is correct
17 Correct 525 ms 45824 KB Output is correct

Subtask #3
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 320 ms 17156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Incorrect 9 ms 5240 KB Output isn't correct
3 Halted 0 ms 0 KB -