제출 #154282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
154282		ryansee	Unique Cities (JOI19_ho_t5)	C++14	0 / 100	188 ms	16588 KiB

joi2019_ho_t5

#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];
void init(ll x,ll par) {
	fdist[x]= depth[x]; p[x]=par;
	for(auto i:v[x]) if(i^par) {
		depth[i]=depth[x]+1; init(i, x);
		fdist[x]=max(fdist[x], fdist[i]);
	}
}
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 p,ll dist) {
	ll cmp=-1;
	for(auto i:v[x]) if(i^p) { if(!F[i]) cmp=max(cmp, fdist[i]-depth[x]); }
	pi mx=pi(dist, 1);
	for(auto i:v[x]) if(i^p) if(F[i]) { 
		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]; 
	} 
	if(mx.f > cmp && mx.s == 1 && mx.f) { // can calc
		ans[x] = 1;
	}
	set <pi,greater<pi>> s;
	for(auto i:v[x])if(i^p){
		fdist[i] -= depth[x];
		s.ins(pi(fdist[i], i));
		fdist[i] += depth[x];
		while(s.size() > 3) s.erase(s.begin());
	}
	s.ins(pi(dist, x));
	while(s.size() > 3) s.erase(s.begin());
	ll o=s.size();
	for(auto i:v[x])if(i^p){
		if(s.begin()->s == i) s.erase(s.begin());
		if(can(s)) dfs(i, x, max(dist,(s.size()?s.begin()->f:0))+1);
		if(siz(s) ^ o) s.ins(pi(fdist[i]-depth[x], i));
	}
}
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);
	FOR(i,1,n) {
		pi ans=pi(0, 1);
		for(auto j:v[i]) if(j^p[i]) {
			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);
	}
	dfs(1, 1, 0);
	FOR(i,1,n) cout<<ans[i]<<"\n";
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32