Submission #624112

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
624112	2022-08-07T09:31:45 Z	Arinoor	LOSTIKS (INOI20_lostiks)	C++17	Compilation error	0 ms	0 KB

Main

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

#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define all(x)			x.begin(), x.end()
#define bug(x)			cout << #x << " : " << x << '\n'
#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e6 + 10;
const int maxm = 30;
const int maxlg = 20;
const int mod = 1e9 + 7;
const ll inf = 1e17 + 10;

int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
int dt[maxm], dl[maxm];
int d[maxm][maxm], l[maxm][maxm];
ll dp[1 << maxlg][maxm];
vector<pii> E;
vector<pii> edge;
vector<int> G[maxn], S;

void dfs(int v, int p = 0, int pe = -1){
	par[v][0] = p;
	if(~pe)
		lck[v][0] = 1 << pe;
	for(int i = 1; i < maxlg and par[v][i - 1]; i ++){
		par[v][i] = par[par[v][i - 1]][i - 1];
		lck[v][i] = lck[v][i - 1] | lck[par[v][i - 1]][i - 1];
	}
	for(int eg : G[v]){
		int u = edge[eg].fi + edge[eg].se - v;
		if(u != p){
			h[u] = h[v] + 1;
			dfs(u, v, e[eg]);
		}
	}
}

int get_par(int v, int h){
	for(int i = 0; i < maxlg; i ++)
		if(h >> i & 1)
			v = par[v][i];
	return v;
}

int get_lock(int v, int h){
	int res = 0;
	for(int i = 0; i < maxlg; i ++){
		if(h >> i & 1){
			res |= lck[v][i];
			v = par[v][i];
		}
	}
	return res;
}

int lca(int v, int u){
	if(h[v] < h[u])
		swap(u, v);
	v = get_par(v, h[v] - h[u]);
	if(v == u)
		return v;
	for(int i = maxlg - 1; ~i; i --){
		if(par[v][i] ^ par[u][i]){
			v = par[v][i];
			u = par[u][i];
		}
	}
	return par[v][0];
}

int dist(int u, int v){
	int w = lca(u, v);
	return h[v] + h[u] - 2 * h[w];
}

int lock_path(int u, int v){
	int w = lca(u, v);
	return get_lock(u, h[u] - h[w]) | get_lock(v, h[v] - h[w]);
}

int main(){
	ios;
	int n, s, t;
	cin >> n >> s >> t;
	for(int i = 0; i < n - 1; i ++){
		int u, v, w;
		cin >> u >> v >> w;
		edge.pb(mp(u, v));
		G[u].pb(i);
		G[v].pb(i);
		if(w){
			e[i] = E.size();
			E.pb(mp(i, w));
		}
		else{
			e[i] = -1;
		}
	}
	dfs(1);
	int m = E.size();
	for(int i = 0; i < m; i ++){
		int u = edge[E[i].fi].fi;
		int v = edge[E[i].fi].se;
		if(dist(E[i].se, u) < dist(E[i].se, v))
			V[i] = u;
		else
			V[i] = v;
		S.pb(V[i]);
	}
	S.pb(s);
	sort(all(S));
	S.resize(unique(all(S)) - S.begin());
	for(int v : S)
		ind[v] = lower_bound(all(S), v) - S.begin();
	n = S.size();
	for(int i = 0; i < n; i ++){
		int v = S[i];
		dt[i] = dist(v, t);
		dl[i] = lock_path(v, t);
		for(int j = 0; j < m; j ++){
			int u = V[j];
			int w = E[j].se;
			d[i][j] = dist(v, w) + dist(w, u);
			l[i][j] = lock_path(v, w) | lock_path(w, u);
		}
	}
	for(int msk = 0; msk < 1 << m; msk ++){
		for(int i = 0; i < n; i ++){
			if(!(dl[i] & msk)){
				dp[msk][i] = dt[i];
				continue;
			}
			dp[msk][i] = inf;
			for(int msk2 = msk; ; msk2 -= msk2 & -msk2){
				if(!msk2) break;
				int bit = __builtin_ctz(msk2);
				if(!(l[i][bit] & msk)){
					dp[msk][i] = min(dp[msk][i], d[i][bit] + dp[msk ^ (1 << bit)][ind[V[bit]]]);
				}
			}
		}
	}
	if(dp[(1 << m) - 1][ind[s]] >= inf)
		cout << "-1\n";
	else
		cout << dp[(1 << m) - 1][ind[s]] << '\n';
}#include <bits/stdc++.h>
using namespace std;

#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define all(x)			x.begin(), x.end()
#define bug(x)			cout << #x << " : " << x << '\n'
#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e6 + 10;
const int maxm = 30;
const int maxlg = 20;
const int mod = 1e9 + 7;
const ll inf = 1e17 + 10;

int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
int dt[maxm], dl[maxm];
int d[maxm][maxm], l[maxm][maxm];
ll dp[1 << maxlg][maxm];
vector<pii> E;
vector<pii> edge;
vector<int> G[maxn], S;

void dfs(int v, int p = 0, int pe = -1){
	par[v][0] = p;
	if(~pe)
		lck[v][0] = 1 << pe;
	for(int i = 1; i < maxlg and par[v][i - 1]; i ++){
		par[v][i] = par[par[v][i - 1]][i - 1];
		lck[v][i] = lck[v][i - 1] | lck[par[v][i - 1]][i - 1];
	}
	for(int eg : G[v]){
		int u = edge[eg].fi + edge[eg].se - v;
		if(u != p){
			h[u] = h[v] + 1;
			dfs(u, v, e[eg]);
		}
	}
}

int get_par(int v, int h){
	for(int i = 0; i < maxlg; i ++)
		if(h >> i & 1)
			v = par[v][i];
	return v;
}

int get_lock(int v, int h){
	int res = 0;
	for(int i = 0; i < maxlg; i ++){
		if(h >> i & 1){
			res |= lck[v][i];
			v = par[v][i];
		}
	}
	return res;
}

int lca(int v, int u){
	if(h[v] < h[u])
		swap(u, v);
	v = get_par(v, h[v] - h[u]);
	if(v == u)
		return v;
	for(int i = maxlg - 1; ~i; i --){
		if(par[v][i] ^ par[u][i]){
			v = par[v][i];
			u = par[u][i];
		}
	}
	return par[v][0];
}

int dist(int u, int v){
	int w = lca(u, v);
	return h[v] + h[u] - 2 * h[w];
}

int lock_path(int u, int v){
	int w = lca(u, v);
	return get_lock(u, h[u] - h[w]) | get_lock(v, h[v] - h[w]);
}

int main(){
	ios;
	int n, s, t;
	cin >> n >> s >> t;
	for(int i = 0; i < n - 1; i ++){
		int u, v, w;
		cin >> u >> v >> w;
		edge.pb(mp(u, v));
		G[u].pb(i);
		G[v].pb(i);
		if(w){
			e[i] = E.size();
			E.pb(mp(i, w));
		}
		else{
			e[i] = -1;
		}
	}
	dfs(1);
	int m = E.size();
	for(int i = 0; i < m; i ++){
		int u = edge[E[i].fi].fi;
		int v = edge[E[i].fi].se;
		if(dist(E[i].se, u) < dist(E[i].se, v))
			V[i] = u;
		else
			V[i] = v;
		S.pb(V[i]);
	}
	S.pb(s);
	sort(all(S));
	S.resize(unique(all(S)) - S.begin());
	for(int v : S)
		ind[v] = lower_bound(all(S), v) - S.begin();
	n = S.size();
	for(int i = 0; i < n; i ++){
		int v = S[i];
		dt[i] = dist(v, t);
		dl[i] = lock_path(v, t);
		for(int j = 0; j < m; j ++){
			int u = V[j];
			int w = E[j].se;
			d[i][j] = dist(v, w) + dist(w, u);
			l[i][j] = lock_path(v, w) | lock_path(w, u);
		}
	}
	for(int msk = 0; msk < 1 << m; msk ++){
		for(int i = 0; i < n; i ++){
			if(!(dl[i] & msk)){
				dp[msk][i] = dt[i];
				continue;
			}
			dp[msk][i] = inf;
			for(int msk2 = msk; ; msk2 -= msk2 & -msk2){
				if(!msk2) break;
				int bit = __builtin_ctz(msk2);
				if(!(l[i][bit] & msk)){
					dp[msk][i] = min(dp[msk][i], d[i][bit] + dp[msk ^ (1 << bit)][ind[V[bit]]]);
				}
			}
		}
	}
	if(dp[(1 << m) - 1][ind[s]] >= inf)
		cout << "-1\n";
	else
		cout << dp[(1 << m) - 1][ind[s]] << '\n';
}

Compilation message

Main.cpp:155:2: error: stray '#' in program
  155 | }#include <bits/stdc++.h>
      |  ^
Main.cpp:155:3: error: 'include' does not name a type
  155 | }#include <bits/stdc++.h>
      |   ^~~~~~~
Main.cpp:169:11: error: redefinition of 'const int maxn'
  169 | const int maxn = 1e6 + 10;
      |           ^~~~
Main.cpp:15:11: note: 'const int maxn' previously defined here
   15 | const int maxn = 1e6 + 10;
      |           ^~~~
Main.cpp:170:11: error: redefinition of 'const int maxm'
  170 | const int maxm = 30;
      |           ^~~~
Main.cpp:16:11: note: 'const int maxm' previously defined here
   16 | const int maxm = 30;
      |           ^~~~
Main.cpp:171:11: error: redefinition of 'const int maxlg'
  171 | const int maxlg = 20;
      |           ^~~~~
Main.cpp:17:11: note: 'const int maxlg' previously defined here
   17 | const int maxlg = 20;
      |           ^~~~~
Main.cpp:172:11: error: redefinition of 'const int mod'
  172 | const int mod = 1e9 + 7;
      |           ^~~
Main.cpp:18:11: note: 'const int mod' previously defined here
   18 | const int mod = 1e9 + 7;
      |           ^~~
Main.cpp:173:10: error: redefinition of 'const ll inf'
  173 | const ll inf = 1e17 + 10;
      |          ^~~
Main.cpp:19:10: note: 'const ll inf' previously defined here
   19 | const ll inf = 1e17 + 10;
      |          ^~~
Main.cpp:175:5: error: redefinition of 'int e [1000010]'
  175 | int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
      |     ^
Main.cpp:21:5: note: 'int e [1000010]' previously declared here
   21 | int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
      |     ^
Main.cpp:175:14: error: redefinition of 'int h [1000010]'
  175 | int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
      |              ^
Main.cpp:21:14: note: 'int h [1000010]' previously declared here
   21 | int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
      |              ^
Main.cpp:175:23: error: redefinition of 'int par [1000010][20]'
  175 | int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
      |                       ^~~
Main.cpp:21:23: note: 'int par [1000010][20]' previously declared here
   21 | int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
      |                       ^~~
Main.cpp:175:41: error: redefinition of 'int lck [1000010][20]'
  175 | int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
      |                                         ^~~
Main.cpp:21:41: note: 'int lck [1000010][20]' previously declared here
   21 | int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
      |                                         ^~~
Main.cpp:175:59: error: redefinition of 'int V [30]'
  175 | int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
      |                                                           ^
Main.cpp:21:59: note: 'int V [30]' previously declared here
   21 | int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
      |                                                           ^
Main.cpp:175:68: error: redefinition of 'int ind [1000010]'
  175 | int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
      |                                                                    ^~~
Main.cpp:21:68: note: 'int ind [1000010]' previously declared here
   21 | int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
      |                                                                    ^~~
Main.cpp:176:5: error: redefinition of 'int dt [30]'
  176 | int dt[maxm], dl[maxm];
      |     ^~
Main.cpp:22:5: note: 'int dt [30]' previously declared here
   22 | int dt[maxm], dl[maxm];
      |     ^~
Main.cpp:176:15: error: redefinition of 'int dl [30]'
  176 | int dt[maxm], dl[maxm];
      |               ^~
Main.cpp:22:15: note: 'int dl [30]' previously declared here
   22 | int dt[maxm], dl[maxm];
      |               ^~
Main.cpp:177:5: error: redefinition of 'int d [30][30]'
  177 | int d[maxm][maxm], l[maxm][maxm];
      |     ^
Main.cpp:23:5: note: 'int d [30][30]' previously declared here
   23 | int d[maxm][maxm], l[maxm][maxm];
      |     ^
Main.cpp:177:20: error: redefinition of 'int l [30][30]'
  177 | int d[maxm][maxm], l[maxm][maxm];
      |                    ^
Main.cpp:23:20: note: 'int l [30][30]' previously declared here
   23 | int d[maxm][maxm], l[maxm][maxm];
      |                    ^
Main.cpp:178:4: error: redefinition of 'll dp [1048576][30]'
  178 | ll dp[1 << maxlg][maxm];
      |    ^~
Main.cpp:24:4: note: 'll dp [1048576][30]' previously declared here
   24 | ll dp[1 << maxlg][maxm];
      |    ^~
Main.cpp:179:13: error: redefinition of 'std::vector<std::pair<int, int> > E'
  179 | vector<pii> E;
      |             ^
Main.cpp:25:13: note: 'std::vector<std::pair<int, int> > E' previously declared here
   25 | vector<pii> E;
      |             ^
Main.cpp:180:13: error: redefinition of 'std::vector<std::pair<int, int> > edge'
  180 | vector<pii> edge;
      |             ^~~~
Main.cpp:26:13: note: 'std::vector<std::pair<int, int> > edge' previously declared here
   26 | vector<pii> edge;
      |             ^~~~
Main.cpp:181:13: error: redefinition of 'std::vector<int> G [1000010]'
  181 | vector<int> G[maxn], S;
      |             ^
Main.cpp:27:13: note: 'std::vector<int> G [1000010]' previously declared here
   27 | vector<int> G[maxn], S;
      |             ^
Main.cpp:181:22: error: redefinition of 'std::vector<int> S'
  181 | vector<int> G[maxn], S;
      |                      ^
Main.cpp:27:22: note: 'std::vector<int> S' previously declared here
   27 | vector<int> G[maxn], S;
      |                      ^
Main.cpp:183:6: error: redefinition of 'void dfs(int, int, int)'
  183 | void dfs(int v, int p = 0, int pe = -1){
      |      ^~~
Main.cpp:29:6: note: 'void dfs(int, int, int)' previously defined here
   29 | void dfs(int v, int p = 0, int pe = -1){
      |      ^~~
Main.cpp:200:5: error: redefinition of 'int get_par(int, int)'
  200 | int get_par(int v, int h){
      |     ^~~~~~~
Main.cpp:46:5: note: 'int get_par(int, int)' previously defined here
   46 | int get_par(int v, int h){
      |     ^~~~~~~
Main.cpp:207:5: error: redefinition of 'int get_lock(int, int)'
  207 | int get_lock(int v, int h){
      |     ^~~~~~~~
Main.cpp:53:5: note: 'int get_lock(int, int)' previously defined here
   53 | int get_lock(int v, int h){
      |     ^~~~~~~~
Main.cpp:218:5: error: redefinition of 'int lca(int, int)'
  218 | int lca(int v, int u){
      |     ^~~
Main.cpp:64:5: note: 'int lca(int, int)' previously defined here
   64 | int lca(int v, int u){
      |     ^~~
Main.cpp:233:5: error: redefinition of 'int dist(int, int)'
  233 | int dist(int u, int v){
      |     ^~~~
Main.cpp:79:5: note: 'int dist(int, int)' previously defined here
   79 | int dist(int u, int v){
      |     ^~~~
Main.cpp:238:5: error: redefinition of 'int lock_path(int, int)'
  238 | int lock_path(int u, int v){
      |     ^~~~~~~~~
Main.cpp:84:5: note: 'int lock_path(int, int)' previously defined here
   84 | int lock_path(int u, int v){
      |     ^~~~~~~~~
Main.cpp:243:5: error: redefinition of 'int main()'
  243 | int main(){
      |     ^~~~
Main.cpp:89:5: note: 'int main()' previously defined here
   89 | int main(){
      |     ^~~~