Submission #469850

#	Time	Username	Problem	Language	Result	Execution time	Memory
469850		MohammadParsaElahimanesh	LOSTIKS (INOI20_lostiks)	C++14	0 / 100	16 ms	23804 KiB

Main

/// In the name of Allah

#include <bits/stdc++.h>

using namespace std;

#define Fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define RFOR(i,a) for(int i = a-1; i >= 0; i--)
#define FOR(i,a) for(int i = 0; i < a; i++)
#define se second
#define fi first
#define sz(x) (int)x.size()
#define upp upper_bound
#define low lower_bound
#define pub push_back
#define all(x) x.begin(),x.end()
#define mp make_pair

typedef double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

const int N = 1'000'000 + 5;
int H[N];
pii dad[N];
vector<pii> G[N];
int n, s, t;
vector<int> way; /// better
bitset<N> L, UL;

void dfs(int v, int h, pii d)
{
	dad[v] = d;
	H[v] = h;
	for(auto u: G[v])if(u.fi != d.fi)dfs(u.fi,h+1,mp(v,u.se));
}

vector<int> f(int st, int en)
{
	cout << st << ' ' << en << endl;
	vector<pii> inv;
	vector<int> road, ex;
	if(H[st] < H[en])
	{
		while(H[st] < H[en])
		{
			inv.pub(mp(en,dad[en].se));
			en = dad[en].fi;
		}
	}
	if(H[st] > H[en])
	{
		while(H[st] > H[en])
		{
			if(dad[st].se && !UL[st])
			{
				if(L[dad[st].fi]){cout << -1;exit(0);}
				L[dad[st].fi] = true;
				ex = f(st,dad[st].se);
				for(auto u: ex)road.pub(u);
				for(int i = sz(ex)-3; i; i--)road.pub(ex[i]);
				UL[st] = true;
			}
			road.pub(st);
			st = dad[st].fi;
		}
	}
	while(st != en)
	{
		inv.pub(dad[en]);
		en = dad[en].fi;
		if(dad[st].se && !UL[st])
		{
			if(L[dad[st].fi]){cout << -1;exit(0);}
			L[dad[st].fi] = true;
			ex = f(st,dad[st].se);
			for(auto u: ex)road.pub(u);
			for(int i = sz(ex)-3; i; i--)road.pub(ex[i]);
			UL[st] = true;
		}
		road.pub(st);
		st = dad[st].fi;
	}
	road.pub(st);
	for(int i = sz(inv)-1; i >= 0; i--)
	{
		if(inv[i].se && !UL[inv[i].fi])
		{
			if(L[inv[i].fi]){cout << -1;exit(0);}
			L[inv[i].fi] = true;
			ex = f(road.back(),inv[i].se);
			for(auto u: ex)road.pub(u);
			for(int i = sz(ex)-3; i >= 0; i--)road.pub(ex[i]);
			UL[inv[i].fi] = true;
		}
		road.pub(inv[i].fi);
	}
	road.pub(-1);
	return road;
}

inline void optimize(vector<int> &A)
{
	if(sz(A) < 3)return;
	vector<int> B;
	for(int i = 0; i < sz(A); i++)
	{
		while((A[i] != -1 && sz(B) >= 2 && A[i] == B[sz(B)-2]))
		{
			B.pop_back();
			B.pop_back();
		}
		while(!B.empty() && B.back() == A[i])B.pop_back();
		B.pub(A[i]);
		//for(auto y: B)cout << y << ' ';
		//cout << '\n';
	}
	A.swap(B);
}

int main()
{
	Fast
	
	/// 1-base-code
	
	/// khod kelidi
	
	cin >> n >> s >> t;
	
	int u, v, k;
	FOR(i,n-1)
	{
		cin >> u >> v >> k;
		G[u].pub(mp(v,k));
		G[v].pub(mp(u,k));
	}
	
	dfs(1,0,mp(-1,-1));
	
	way = f(s,t);
	//for(auto u: way)cout << u << ' ';
	//cout << '\n';
	optimize(way);
	//for(auto u: way)cout << u << ' ';
	//cout << '\n';
	int ans = -1;
	for(auto u: way)if(u != -1)ans++;
	cout << ans;
	
	return 0;
}

// thank god

• Subtask 1: 0 / 23
• Subtask 2: 0 / 36
• Subtask 3: 0 / 41