Submission #469858

#	Time	Username	Problem	Language	Result	Execution time	Memory
469858		MohammadParsaElahimanesh	LOSTIKS (INOI20_lostiks)	C++14	0 / 100	63 ms	29424 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)
{
	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>=0; i--)road.pub(ex[i]);
				UL[st] = true;
				road.pub(-1);
			}
			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>=0; i--)road.pub(ex[i]);
			UL[st] = true;
			road.pub(-1);
		}
		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(-1);
		}
		road.pub(inv[i].fi);
	}
	road.pub(-1);
	return road;
}

inline void optimize(vector<int> &A)
{
	vector<int> B = A;
	B.resize(unique(all(B))-B.begin());
	A.swap(B);
	B.clear();
	for(auto u: A)
	{
		if(u == -1)
		{
			if(!B.empty())B[sz(B)-1] = -abs(B[sz(B)-1]);
		}
		else
		{
			B.pub(u);
		}
	}
	A.swap(B);
	B.clear();
	for(auto u: A)
	{
		if(sz(B) >= 2 && abs(u) == abs(B[sz(B)-2]) && B.back() >= 0)
		{
			if(B[sz(B)-2] < 0)u = -abs(u);
			B.pop_back();B.pop_back();
		}
		B.pub(u);
	}
	A.swap(B);
	for(auto &u: A)u = abs(u);
	A.resize(unique(all(A))-A.begin());
}

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);

	optimize(way);

	cout << sz(way)-1;
	
	return 0;
}

// thank god

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