Submission #1043444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043444		javotaz	LOSTIKS (INOI20_lostiks)	C++17	59 / 100	2033 ms	216260 KiB

Main

// In the Name of Allah

#include<bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("Ofast,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,avx,avx2,sse4.2,popcnt,tune=native")

typedef long long ll;

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()

const int N = 1e6 + 12, M = 20, inf = 2e9 + 7;
vector<pii> g[N];
int n, s, t, par[N], dp[(1 << M) + 4][M], p[N], kd[N], bt[M], sz, pd[N], e[N], l[N];
vector<int> q[(1 << M)];
pii f[2 * M + 2][2 * M + 2];
bool mrk[N];
vector<int> v, d;

struct node {
	int u, h, mask, par;
};

void ip() {
	cin >> n >> s >> t;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
}

void dfs(int u) {
	for (auto i: g[u])
		if (i.F != par[u]) { 
			par[i.F] = u;
			e[i.F] = e[u] + 1;
			if (i.S) {
				pd[i.F] = d.size(), d.pb(i.F), kd[i.F] = i.S;
				v.pb(u), v.pb(i.S);
			}
			dfs(i.F);
		}
}

void bfs(int u, int rt) {
	node st;
	st.par = st.u = u, st.h = st.mask = 0;
	vector<node> v;
	v.pb(st);
	while (!v.empty()) {
		node tmp = v.back();
		v.pp();
		if (mrk[tmp.u])
			f[rt][p[tmp.u]] = {tmp.h, tmp.mask};
		for (auto i: g[tmp.u])
			if (i.F != tmp.par) {
				node tmp2;
				tmp2.u = i.F, tmp2.h = tmp.h + 1, tmp2.par = tmp.u;
				tmp2.mask = (i.S? (tmp.mask | (1 << pd[(e[tmp.u] < e[i.F])? i.F : tmp.u])) : tmp.mask);
				v.pb(tmp2);
			}
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ip();
	par[s] = s;
	dfs(s);
	v.pb(s), v.pb(t);
	sort(all(v));
	v.resize(unique(all(v)) - v.begin());
	for (int i = 0; i < v.size(); i++) 
		p[v[i]] = i, mrk[v[i]] = true;
	for (int i = 0; i < v.size(); i++)
		bfs(v[i], i);
	memset(dp, 127, sizeof dp);
	int c = d.size();
	for (int i = 0; i < c; i++)
		l[i] = p[par[d[i]]];
	int ans = inf;
	for (int mask = 1; mask < (1 << c); ++mask) {
		sz = 0;
		for (char i = 0; i < c; i++)
			if ((mask >> i) & 1)
				bt[sz++] = i;
		for (char id1 = 0; id1 < sz; ++id1) {
			int i = bt[id1];
			int u = d[i], ku = kd[d[i]], x = mask ^ (1 << i);
			int v1 = f[p[ku]][p[par[u]]].F;
			auto &dd = dp[mask][i];
			auto &bb = f[p[ku]];
			if (__builtin_popcount(mask) == 1) {
				if (f[p[s]][p[ku]].S == x && f[p[ku]][l[i]].S == x)
					dp[mask][i] = f[p[s]][p[ku]].F + v1;
			}
			else if ((f[p[ku]][l[i]].S | x) == x) {
				for (auto j: q[x])
					if ((bb[l[j]].S | x) == x)
						dd = min(dd, dp[x][j] + bb[l[j]].F);
				if (dd < inf)
					dd += v1;
			}
			if ((f[p[par[u]]][p[t]].S | mask) == mask)
				ans = min(ans, dp[mask][i] + f[p[par[u]]][p[t]].F);
			if (dp[mask][i] < inf)
				q[mask].pb(i);
		}
	}
	if (f[p[s]][p[t]].S == 0)
		ans = f[p[s]][p[t]].F;
	cout << ((ans == inf)? -1 : ans) << '\n';

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for (int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
Main.cpp:83:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for (int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
Main.cpp:96:15: warning: array subscript has type 'char' [-Wchar-subscripts]
   96 |    int i = bt[id1];
      |               ^~~

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