Submission #1319980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319980		JuanJL	Unique Cities (JOI19_ho_t5)	C++20	0 / 100	510 ms	339968 KiB

joi2019_ho_t5

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef int ll;

const int MAXN = 200000+5;

ll n,m;
vector<ll> adj[MAXN];
ll dist1[MAXN];
ll dist2[MAXN];
ll len1[MAXN];
ll len2[MAXN];
ll eti[MAXN];

void dfs(ll nd, ll p,ll dis, ll t){
	if(t==1){
		dist1[nd]=dis;
		len1[nd]=1;
	}else{
		dist2[nd]=dis;
		len2[nd]=1;
	}

	for(auto i:adj[nd]) if(i!=p){
		dfs(i,nd,dis+1,t);
		if(t==1) len1[nd]=max(len1[nd],len1[i]+1);
		else len2[nd]=max(len2[nd],len2[i]+1);
	}
}

bool cmp1(ll a, ll b){
	return len1[a]>len1[b];
}

bool cmp2(ll a, ll b){
	return len2[a]>len2[b];
}

ll res1[MAXN];
stack<pair<ll,ll>> pila1;
vector<pair<ll,ll>> er1[MAXN];
void ndfs1(ll nd, ll p, ll dis){
		ll mlen = max(((SZ(adj[nd])>0 && adj[nd][0]!=p)?len1[adj[nd][0]]:0),((SZ(adj[nd])>1 && adj[nd][1]!=p)?len1[adj[nd][1]]:0));
		
		while(!pila1.empty() && pila1.top().fst>=dis-mlen){
			er1[nd].pb(pila1.top());
			pila1.pop();
		}

		/*cout<<nd<<" "<<p<<": ";
		stack<pair<ll,ll>> rare = pila1; while(!rare.empty()) cout<<rare.top().snd<<" ", rare.pop(); cout<<'\n';*/

		res1[nd]=SZ(pila1);

		while(!er1[nd].empty()){
					pila1.push(er1[nd].back());
					er1[nd].pop_back();
				}
		

		mlen=0;
		for(auto i:adj[nd]) if(i!=p){
			for(auto j:adj[nd]) if(j!=p && j!=i) mlen=max(mlen,len1[j]);

			while(!pila1.empty() && pila1.top().fst>=dis-mlen){
						er1[nd].pb(pila1.top());
						pila1.pop();
					}
			pila1.push({dis,nd});
			ndfs1(i,nd,dis+1);	
			pila1.pop();
			while(!er1[nd].empty()){
								pila1.push(er1[nd].back());
								er1[nd].pop_back();
							}

			
		}


		
}	

ll res2[MAXN];
stack<pair<ll,ll>> pila2;
vector<pair<ll,ll>> er2[MAXN];
void ndfs2(ll nd, ll p, ll dis){
	
		ll mlen = max(((SZ(adj[nd])>0 && adj[nd][0]!=p)?len2[adj[nd][0]]:0),((SZ(adj[nd])>1 && adj[nd][1]!=p)?len2[adj[nd][1]]:0));

		while(!pila2.empty() && pila2.top().fst>=dis-mlen){
			er2[nd].pb(pila2.top());
			pila2.pop();
		}
		/*cout<<nd<<" "<<p<<": ";
			stack<pair<ll,ll>> rare = pila2; while(!rare.empty()) cout<<rare.top().snd<<" ", rare.pop(); cout<<'\n';*/
		res2[nd]=SZ(pila2);

			while(!er2[nd].empty()){
						pila2.push(er2[nd].back());
						er2[nd].pop_back();
					}	
		mlen=0;	
		for(auto i:adj[nd]) if(i!=p){

			for(auto j:adj[nd]) if(j!=p && j!=i) mlen=max(mlen,len2[j]);
					while(!pila2.empty() && pila2.top().fst>=dis-mlen){
						er2[nd].pb(pila2.top());
						pila2.pop();
					}
			
		
				pila2.push({dis,nd});
			ndfs2(i,nd,dis+1);
			pila2.pop();
			while(!er2[nd].empty()){
						pila2.push(er2[nd].back());
						er2[nd].pop_back();
					}	
		}
}

int main(){
	cin>>n>>m;

	ll u,v;
	forn(i,0,n-1){
		cin>>u>>v; u--; v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}


	forn(i,0,n) cin>>eti[i];

	dfs(0,-1,0,1);
	pair<ll,ll> d1 = {-1,0}; forn(i,0,n) d1=max(d1,{dist1[i],i});

	dfs(d1.snd,-1,0,1);
	pair<ll,ll> d2 = {-1,0}; forn(i,0,n) d2=max(d2,{dist1[i],i});

	dfs(d2.snd,-1,0,2);

	forn(i,0,n){
		sort(ALL(adj[i]),cmp1);
	}
	/*cout<<d1.snd<<" "<<d2.snd<<'\n';	
	cout<<"arranca el real process\n";*/
	ndfs1(d1.snd,-1,0);

	forn(i,0,n){
		sort(ALL(adj[i]),cmp2);
	}

	//cout<<"---------------------------------------\n";
	ndfs2(d2.snd,-1,0);

	forn(i,0,n){
		if(dist1[i]>dist2[i]) cout<<res1[i]<<'\n';
		else cout<<res2[i]<<'\n';
	}
	return 0;
}

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