Submission #90443

#TimeUsernameProblemLanguageResultExecution timeMemory
90443inomEvacuation plan (IZhO18_plan)C++14
54 / 100
876 ms22764 KiB
#include<bits/stdc++.h> #include<ext/pb_ds/tree_policy.hpp> #include<ext/pb_ds/assoc_container.hpp> #define fi first #define se second #define new new228 #define pb push_back #define rank rank228 #define sz(c) (int)(c).size() #define all(c) (c).begin(), (c).end() #define rall(c) (c).rbegin(), (c).rend() using namespace std; using namespace __gnu_pbds; #pragma GCC optimize("Ofast") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") #pragma GCC optimize("fast-math") #pragma warning(disable : 4996) typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // st.oreder_of_key(); const int N = 100100; const int MAXN = 4 * N; const int INF = 1e9 + 7; const int MOD = 998244353; int TN = 1; int n, m, k, q; int a[N], d[N], c[N], f[20][20]; vector<pair<int, int>> verr[N]; void subtask12() { for (int i = 1; i <= n; i++) { d[i] = INF; } set<pair<int, int>> st; for (int i = 1; i <= k; i++) { d[a[i]] = 0; st.insert({d[a[i]], a[i]}); } while (!st.empty()) { int x = st.begin()->se; st.erase(st.begin()); for (auto i: verr[x]) { int to = i.fi, len = i.se; if (d[x] + len < d[to]) { st.erase({d[to], to}); d[to] = d[x] + len; st.insert({d[to], to}); } } } while (q--) { int x, y; scanf("%d %d", &x, &y); printf("%d\n", min(d[x], d[y])); } return; } void subtask3() { //printf("I'm here :)\n"); for (int i = 1; i <= n; i++) { d[i] = INF; } set<pair<int, int>> st; for (int i = 1; i <= k; i++) { d[a[i]] = 0; st.insert({d[a[i]], a[i]}); } while (!st.empty()) { int x = st.begin()->se; st.erase(st.begin()); for (auto i: verr[x]) { int to = i.fi, len = i.se; if (d[x] + len < d[to]) { st.erase({d[to], to}); d[to] = d[x] + len; st.insert({d[to], to}); } } } /*for (int i = 1; i <= n; i++) { printf("%d ", d[i]); } puts(""); */for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { f[i][j] = -1; } } for (int from = 1; from <= n; from++) { for (auto to: verr[from]) { f[from][to.fi] = min(d[from], d[to.fi]); } } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { //f[i][j] = max(min(d[i], d[j]), min(d[i], min(d[j], d[k]))); f[i][j] = max(f[i][j], min(f[i][k], f[k][j])); } } } while (q--) { int x, y; scanf("%d %d", &x, &y); printf("%d\n", f[x][y]); } return; } void subtask4a() { set<pair<int, int>> st; for (int i = 1; i <= n; i++) { d[i] = INF; } for (int i = 1; i <= k; i++) { d[a[i]] = 0; st.insert({d[a[i]], a[i]}); } while (!st.empty()) { int x = st.begin()->se; st.erase(st.begin()); for (auto i: verr[x]) { int to = i.fi, len = i.se; if (d[x] + len < d[to]) { st.erase({d[to], to}); d[to] = d[x] + len; st.insert({d[to], to}); } } } int x, y; scanf("%d %d", &x, &y); st.clear(); d[x] = min(d[x], d[y]); st.insert({d[x], x}); while (!st.empty()) { int v = st.begin()->se; st.erase(st.begin()); for (auto i: verr[v]) { int to = i.fi; if (d[to] < min(d[v], d[to])) { st.erase({d[to], to}); d[to] = min(d[v], d[to]); st.insert({d[to], to}); } } } for (int i = 1; i <= n; i++) { printf("%d ", d[i]); } printf("%d\n", d[y]); return; } void dfs(int x, int val) { c[x] = 1; for (auto i: verr[x]) { if (c[i.fi] || d[i.fi] < val) { continue; } dfs(i.fi, val); } } void subtask4() { for (int i = 1; i <= n; i++) { d[i] = INF; } set<pair<int, int>> st; for (int i = 1; i <= k; i++) { d[a[i]] = 0; st.insert({d[a[i]], a[i]}); } while (!st.empty()) { int x = st.begin()->se; st.erase(st.begin()); for (auto i: verr[x]) { int to = i.fi, len = i.se; if (d[x] + len < d[to]) { st.erase({d[to], to}); d[to] = d[x] + len; st.insert({d[to], to}); } } } int x, y; scanf("%d %d", &x, &y); int l = 0, r = d[x]; while (l <= r) { int mid = (l + r) >> 1; fill(c + 1, c + 1 + n, 0); c[x] = 1; dfs(x, mid); if (c[y]) { l = mid + 1; } else { r = mid - 1; } } // printf("%d %d\n", l, r); /*fill(c + 1, c + 1 + n, 0); c[x] = 1; dfs(x, r); if (c[y]) { l = r; }*/ printf("%d\n", --l); return; } signed main() { // ios_base::sync_with_stdio(0); // cin.tie(nullptr); cout.tie(nullptr); // in; out; // cin >> TN; // while (TN--) { solve(); } scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { int x, y, cost; scanf("%d %d %d", &x, &y, &cost); verr[x].pb({y, cost}); verr[y].pb({x, cost}); } scanf("%d", &k); for (int i = 1; i <= k; i++) { scanf("%d", &a[i]); } scanf("%d", &q); if (q == 1) { subtask4(); return 0; } if (n <= 15 && m <= 200 && q <= 200) { subtask3(); return 0; } if (n <= 100000 && m <= 5 * 100000 && q <= 100000) { subtask12(); return 0; } return 0; }

Compilation message (stderr)

plan.cpp:22:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)
 
plan.cpp: In function 'void subtask12()':
plan.cpp:58:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d %d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp: In function 'void subtask3()':
plan.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp: In function 'void subtask4a()':
plan.cpp:136:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &x, &y);
  ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp: In function 'void subtask4()':
plan.cpp:189:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &x, &y);
  ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:218:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:221:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d %d %d", &x, &y, &cost);
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:224:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
plan.cpp:226:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &a[i]);
      ~~~~~^~~~~~~~~~~~~
plan.cpp:228:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
#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...