Submission #167158

#TimeUsernameProblemLanguageResultExecution timeMemory
167158LightningEvacuation plan (IZhO18_plan)C++17
10 / 100
4046 ms21880 KiB
#include <iostream> #include <algorithm> #include <vector> #include <set> using namespace std; typedef pair <int, int> pii; #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define pb push_back #define mkp make_pair #define F first #define S second const int N = 1e5 + 5; const int INF = 1e9 + 5; int n, m, k, q; vector <pii> g[N]; vector <int> new_gr[N]; set <pii> st; int dist[N], up[N][18], pr[N], tin[N], tout[N], tiktak; bool was[N]; void dijkstra() { while(sz(st)) { int v = st.begin() -> S; st.erase(st.begin()); for(pii it : g[v]) { int w = it.F; int to = it.S; if(dist[to] > dist[v] + w) { st.erase(mkp(dist[to], to)); dist[to] = dist[v] + w; st.insert(mkp(dist[to], to)); } } } } int get_par(int v) { if(pr[v] == v) return v; return get_par(pr[v]); } void dfs(int v, int pre) { tin[v] = ++tiktak; up[v][0] = pre; for(int i = 1; i <= 17; ++i) { up[v][i] = up[up[v][i - 1]][i - 1]; } for(int to : new_gr[v]) { if(to != pre) dfs(to, v); } tout[v] = ++tiktak; } bool upper(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); } int lca(int a, int b) { if(upper(a, b)) return a; if(upper(b, a)) return b; for(int i = 17; i >= 0; --i) { if(!upper(up[a][i], b)) { a = up[a][i]; break; } } return up[a][0]; } int main () { scanf("%d%d", &n, &m); for(int i = 1; i <= m; ++i) { int a, b, c; scanf("%d%d%d", &a, &b, &c); g[a].pb(mkp(c, b)); g[b].pb(mkp(c, a)); } for(int i = 1; i <= n; ++i) dist[i] = INF, pr[i] = i; scanf("%d", &k); for(int i = 1; i <= k; ++i) { int b; scanf("%d", &b); dist[b] = 0; st.insert(mkp(0, b)); } dijkstra(); vector <pii> vec; for(int i = 1; i <= n; ++i) { vec.pb(mkp(dist[i], i)); } sort(all(vec)); for(int i = sz(vec) - 1 ; i >= 0; --i) { int v = vec[i].S; was[v] = 1; for(pii it : g[v]) { int to = it.S; int par_to = get_par(to); if(was[to] && v != par_to) { pr[par_to] = v; new_gr[v].pb(par_to); new_gr[par_to].pb(v); } } } dfs(vec[0].S, vec[0].S); scanf("%d", &q); for(int it = 1; it <= q; ++it) { int s, t; scanf("%d%d", &s, &t); int lc = lca(s, t); printf("%d\n", dist[lc]); } return 0; }

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);  
  ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);  
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
  ~~~~~^~~~~~~~~~
plan.cpp:78:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int b; scanf("%d", &b);
          ~~~~~^~~~~~~~~~
plan.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
plan.cpp:104:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, t; scanf("%d%d", &s, &t);
             ~~~~~^~~~~~~~~~~~~~~~
#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...