Submission #495302

#	Time	Username	Problem	Language	Result	Execution time	Memory
495302		Ziel	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1727 ms	145684 KiB

plan

/**
 * LES GREATEABLES BRO TEAM
**/

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define sz(x) (int)x.size()
const bool FLAG = false;
void setIO(const string &f = "");

string to_string(const string s) {
	return '"' + s + '"';
}
string to_string(const char c) {
 	return char(39) + string(1, c) + char(39);
}
string to_string(const char* s) {
 	return to_string(string(s));
}
string to_string(bool f) {
	return (f ? "true" : "false");
}
template<class A, class B>
string to_string(const pair<A, B> x) {
	return "(" + to_string(x.first) + ", " + to_string(x.second) + ")";
}
template<class A, class B, class C>
string to_string(const tuple<A, B, C> x) {
	return "(" + to_string(get<0>(x)) + ", " + to_string(get<1>(x)) + ", " + to_string(get<2>(x)) + ")";
}
template<class A, class B, class C, class D>
string to_string(const tuple<A, B, C, D> x) {
	return "(" + to_string(get<0>(x)) + ", " + to_string(get<1>(x)) + ", " + to_string(get<2>(x)) + ", " + to_string(get<3>(x)) + ")";
}
template<class T>
string to_string(const T v) {
	string res = "{"; bool f = true;
	for (auto x: v)
		res += (f ? to_string(x) : ", " + to_string(x)), f = false;
	return res + "}";
}
void debug_args() { cerr << "]\n"; }
template<class H, class... T>
void debug_args(H x, T... y) {
	cerr << to_string(x);
	if (sizeof... (y))
	cerr << ", ";
	debug_args(y...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: [", debug_args(__VA_ARGS__);
#else
#define debug(...) 47
#endif

#define int ll

const int N = 1e6 + 13, L = 23, INF = 1e12 + 15;

struct Edge {
	int x, y, w1, w2;
};

bool visited[N];
ll up[L][N], mx[L][N], comp[N], par[N], siz[N], level[N], d[N];
vector<vector<int>> adj2(N);

int find_set(int x) {
	if (x == par[x])
		return x;
	return par[x] = find_set(par[x]);
}
void union_sets(int a, int b) {
	a = find_set(a);
	b = find_set(b);
	if (a != b) {
		if (siz[a] < siz[b])
			swap(a, b);
		siz[a] += siz[b];
		par[b] = a;
	}
}

void dfs(int c, int v, int pr) {
	visited[v] = 1;
	comp[v] = c;
	up[0][v] = pr;
	mx[0][v] = min(d[v], d[pr]);
	level[v] = level[pr] + 1;
	for (int i = 1; i < 21; i++) {
		up[i][v] = up[i - 1][up[i - 1][v]];
		mx[i][v] = min(mx[i - 1][v], mx[i - 1][up[i - 1][v]]);
	}
	for (auto to: adj2[v]) {
		if (to != pr)
			dfs(c, to, v);
	}
}
int lca(int a, int b) {
	if (level[a] > level[b])
		swap(a, b);
	int res = INF;
	for (int i = 20; i >= 0; i--) {
		if (level[a] <= level[up[i][b]]) {
			debug(a, level[a], b, i, up[i][b], level[up[i][b]]);
			debug(mx[i][b], i, b);
			res = min(res, mx[i][b]);
			b = up[i][b];
		}
	}
	if (a == b)
		return res;
	for (int i = 20; i >= 0; i--) {
		if (up[i][a] != up[i][b]) {
			debug(mx[i][a], i, a);
			debug(mx[i][b], i, b);
			res = min(res, min(mx[i][a], mx[i][b]));
			a = up[i][a];
			b = up[i][b];
		}
	}
	debug(mx[0][a], 0, a);
	debug(mx[0][b], 0, b);
	res = min(res, min(mx[0][a], mx[0][b]));
	res = min(res, d[up[0][a]]);
	return res;
}

signed main() {
    setIO();
    
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);
    set<pair<int, int>> edges;
    for (int i = 0, x, y, z; i < m; i++) {
    	cin >> x >> y >> z;
    	adj[x].push_back({y, z});
    	adj[y].push_back({x, z});
    	edges.insert({min(x, y), max(x, y)});
    }
    for (int i = 0; i <= 21; i++)
    	for (int j = 0; j <= n + 2; j++)
    		mx[i][j] = INF, d[j] = INF;

    int k;
    cin >> k;
    vector<int> g(k + 1);
    set<int> npp;
    for (int i = 1; i <= k; i++) {
    	cin >> g[i];
    	npp.insert(g[i]);
    }

    {
    	set<pair<int, int>> q;
    	for (int i = 1; i <= k; i++) {
    		q.insert({0, g[i]});
    		d[g[i]] = 0;
    	}
		while (sz(q)) {
			int v = q.begin()->second;
			q.erase(q.begin());

			for (auto [to, len]: adj[v]) {
				if (d[to] > d[v] + len) {
					q.erase({d[to], to});
					d[to] = d[v] + len;
					q.insert({d[to], to});
				}
			}
		}
    }

    vector<Edge> mst;
    for (auto [x, y]: edges) {
    	if (!npp.count(x) && !npp.count(y)) {
    		Edge cur;
    		cur.x = x, cur.y = y;
    		cur.w1 = min(d[x], d[y]), cur.w2 = max(d[x], d[y]);
    		mst.push_back(cur);
    	}
    }
    bool flag12 = true;
    if (sz(mst)) {
	    sort(mst.begin(), mst.end(), [](Edge x, Edge y) {
    		if (x.w1 == y.w1)
    			return x.w2 > y.w2;
	    	return x.w1 > y.w1;
    	});
	    for (int i = 1; i <= n; i++)
    		par[i] = i, siz[i] = 1;
	    for (auto x: mst) {
    		if (find_set(x.x) != find_set(x.y)) {
    			union_sets(x.x, x.y);
    			adj2[x.x].push_back(x.y);
	    		adj2[x.y].push_back(x.x);
    		}
	    }
    	int comp_id = 1;
	    for (int i = 1; i <= n; i++) {
    		if (!visited[i]) {
    			dfs(comp_id, i, 0);
    			comp_id++;
	    	}
    	}
    } else
    	flag12 = false;

    int qr;
    cin >> qr;

    while (qr--) {
    	int s, t;
    	cin >> s >> t;
    	if (!flag12) {
    		cout << "0\n";
    		continue;
    	}
    	if (edges.count({min(s, t), max(s, t)})) {
    		cout << min(d[s], d[t]) << '\n';
    	} else if ((npp.count(s) || npp.count(t)) || (comp[s] != comp[t])) {
    		cout << "0\n";
    	} else {
    		cout << lca(s, t) << '\n';
    	}
    }

    
    return 0;
}

void setIO(const string &f) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen((f + ".in").c_str(), "r")) {
        freopen((f + ".in").c_str(), "r", stdin);
        freopen((f + ".out").c_str(), "w", stdout);
    }
}

Compilation message (stderr)

plan.cpp: In function 'll lca(ll, ll)':
plan.cpp:57:20: warning: statement has no effect [-Wunused-value]
   57 | #define debug(...) 47
      |                    ^~
plan.cpp:109:4: note: in expansion of macro 'debug'
  109 |    debug(a, level[a], b, i, up[i][b], level[up[i][b]]);
      |    ^~~~~
plan.cpp:57:20: warning: statement has no effect [-Wunused-value]
   57 | #define debug(...) 47
      |                    ^~
plan.cpp:110:4: note: in expansion of macro 'debug'
  110 |    debug(mx[i][b], i, b);
      |    ^~~~~
plan.cpp:57:20: warning: statement has no effect [-Wunused-value]
   57 | #define debug(...) 47
      |                    ^~
plan.cpp:119:4: note: in expansion of macro 'debug'
  119 |    debug(mx[i][a], i, a);
      |    ^~~~~
plan.cpp:57:20: warning: statement has no effect [-Wunused-value]
   57 | #define debug(...) 47
      |                    ^~
plan.cpp:120:4: note: in expansion of macro 'debug'
  120 |    debug(mx[i][b], i, b);
      |    ^~~~~
plan.cpp:57:20: warning: statement has no effect [-Wunused-value]
   57 | #define debug(...) 47
      |                    ^~
plan.cpp:126:2: note: in expansion of macro 'debug'
  126 |  debug(mx[0][a], 0, a);
      |  ^~~~~
plan.cpp:57:20: warning: statement has no effect [-Wunused-value]
   57 | #define debug(...) 47
      |                    ^~
plan.cpp:127:2: note: in expansion of macro 'debug'
  127 |  debug(mx[0][b], 0, b);
      |  ^~~~~
plan.cpp: In function 'void setIO(const string&)':
plan.cpp:241:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  241 |         freopen((f + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:242:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  242 |         freopen((f + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46