Submission #527444

#TimeUsernameProblemLanguageResultExecution timeMemory
527444SmolBrainEvacuation plan (IZhO18_plan)C++17
100 / 100
932 ms74688 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int, int> pii; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define endl '\n' #define pb push_back #define conts continue #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define ff first #define ss second #define ceil2(x,y) ((x+y-1) / (y)) #define sz(a) a.size() #define setbits(x) __builtin_popcountll(x) #ifndef ONLINE_JUDGE #define debug(x) cout << #x <<" = "; print(x); cout << endl #else #define debug(x) #endif #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define trav(i,a) for(auto &i : a) bool iseven(ll n) {if ((n & 1) == 0) return true; return false;} void print(ll t) {cout << t;} void print(int t) {cout << t;} void print(string t) {cout << t;} void print(char t) {cout << t;} void print(double t) {cout << t;} void print(ld t) {cout << t;} template <class T, class V> void print(pair <T, V> p); template <class T> void print(vector <T> v); template <class T> void print(set <T> v); template <class T, class V> void print(map <T, V> v); template <class T> void print(multiset <T> v); template <class T, class V> void print(pair <T, V> p) {cout << "{"; print(p.ff); cout << ","; print(p.ss); cout << "}";} template <class T> void print(vector <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";} template <class T> void print(set <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";} template <class T> void print(multiset <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";} template <class T, class V> void print(map <T, V> v) {cout << "[ "; for (auto i : v) {print(i); cout << " ";} cout << "]";} template<typename T> void amin(T &a, T b) { a = min(a, b); } template<typename T> void amax(T &a, T b) { a = max(a, b); } void usaco(string filename) { freopen((filename + ".in").c_str(), "r", stdin); freopen((filename + ".out").c_str(), "w", stdout); } const int MOD = 1e9 + 7; const int maxn = 1e5 + 5; const int inf1 = 1e9 + 5; const ll inf2 = ll(1e18) + 5; const int LOG = 17; struct DSU { // DSU data structure with 1-based indexing vector<int> par, rankk; DSU() { } DSU(int n) { init(n); } void init(int n) { par = vector<int>(n + 1); rankk = vector<int>(n + 1); rep1(i, n) create(i); } void create(int u) { par[u] = u; rankk[u] = 0; } int find(int u) { if (u == par[u]) return u; else return par[u] = find(par[u]); } bool same(int u, int v) { return find(u) == find(v); } void merge(int u, int v) { u = find(u), v = find(v); if (u == v) return; if (rankk[u] == rankk[v]) rankk[u]++; if (rankk[u] < rankk[v]) swap(u, v); par[v] = u; } }; vector<pii> adj[maxn], adj2[maxn]; vector<int> dis(maxn); vector<bool> vis(maxn); vector<vector<int>> up(maxn, vector<int>(LOG, 1)), mnedge(maxn, vector<int>(LOG, inf1)); vector<int> depth(maxn); void dfs(int node, int par) { for (auto [child, w] : adj2[node]) { if (child == par) conts; up[child][0] = node; rep1(j, LOG - 1) { up[child][j] = up[ up[child][j - 1] ][j - 1]; } mnedge[child][0] = w; rep1(j, LOG - 1) { mnedge[child][j] = min(mnedge[child][j - 1], mnedge[ up[child][j - 1] ][j - 1]); } depth[child] = depth[node] + 1; dfs(child, node); } } pii lift(int u, int k) { int mn = inf1; rep(j, LOG) { int f = 1 << j; if (k & f) { amin(mn, mnedge[u][j]); u = up[u][j]; } } return {u, mn}; } pii lca(int u, int v) { int mn = inf1; if (depth[u] < depth[v]) swap(u, v); int k = depth[u] - depth[v]; auto res = lift(u, k); u = res.ff, mn = res.ss; if (u == v) return {u, mn}; for (int j = LOG - 1; j >= 0; --j) { if (up[u][j] != up[v][j]) { amin(mn, mnedge[u][j]); amin(mn, mnedge[v][j]); u = up[u][j]; v = up[v][j]; } } amin(mn, mnedge[u][0]); amin(mn, mnedge[v][0]); u = up[u][0]; return {u, mn}; } int getmn(int u, int v) { auto [l, mn] = lca(u, v); return mn; } void solve(int test_case) { int n, m; cin >> n >> m; rep(i, m) { int u, v, w; cin >> u >> v >> w; adj[u].pb({v, w}), adj[v].pb({u, w}); } int k; cin >> k; priority_queue<pii, vector<pii>, greater<pii> > pq; rep(i, k) { int u; cin >> u; pq.push({0, u}); dis[u] = 0; } while (!pq.empty()) { auto [cost, node] = pq.top(); pq.pop(); if (vis[node]) conts; vis[node] = 1; dis[node] = cost; for (auto [child, w] : adj[node]) { pq.push({cost + w, child}); } } vector<array<int, 3>> edges; rep1(node, n) { for (auto [child, w] : adj[node]) { int weight = min(dis[node], dis[child]); edges.pb({weight, node, child}); } } sort(rall(edges)); DSU dsu(n); for (auto [w, u, v] : edges) { if (dsu.same(u, v)) conts; dsu.merge(u, v); adj2[u].pb({v, w}), adj2[v].pb({u, w}); } dfs(1, -1); int q; cin >> q; while (q--) { int u, v; cin >> u >> v; int ans = getmn(u, v); cout << ans << endl; } } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } return 0; }

Compilation message (stderr)

plan.cpp: In function 'void usaco(std::string)':
plan.cpp:59:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:60:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...