Submission #630508

#TimeUsernameProblemLanguageResultExecution timeMemory
630508QwertyPiRobot (JOI21_ho_t4)C++14
0 / 100
432 ms30092 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define fi first #define se second #define int long long using namespace std; const int N = 100013, M = 400013; int a[M], b[M], c[M], p[M]; vector<int> G[N]; int d[M][2]; bool vis[M][2]; vector<int> gc[N], s[N]; int getM(int i, int colour){ int l = lower_bound(gc[i].begin(), gc[i].end(), colour) - gc[i].begin() - 1; int r = upper_bound(gc[i].begin(), gc[i].end(), colour) - gc[i].begin() - 1; return s[i][r] - s[i][l]; } int32_t main(){ int n, m; cin >> n >> m; a[0] = 0, b[0] = 1, c[0] = 0, p[0] = 0; for(int i = 1; i <= m; i++){ cin >> a[i] >> b[i] >> c[i] >> p[i]; G[a[i]].push_back(i); a[m + i] = b[i], b[m + i] = a[i], c[m + i] = c[i], p[m + i] = p[i]; G[a[m + i]].push_back(m + i); } priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq; pq.push({0, {0, 0}}); vis[0][0] = true; for(int i = 1; i <= m * 2; i++){ d[i][0] = d[i][1] = (1LL << 60); } for(int i = 1; i <= n; i++){ vector<pair<int, int>> v; for(auto j : G[i]){ v.push_back({c[j], p[j]}); } sort(v.begin(), v.end()); gc[i].push_back(0); s[i].push_back(0); for(auto j : v){ gc[i].push_back(j.fi); s[i].push_back(s[i].back() + j.se); } for(auto j : gc[i]) cout << j << ' '; cout << endl; for(auto j : s[i]) cout << j << ' '; cout << endl; } while(pq.size()){ pair<int, pii> t = pq.top(); pq.pop(); int dis = t.fi, eid = t.se.fi, r = t.se.se; if(d[eid][r] < dis) continue; vis[eid][r] = true; int u = a[eid], v = b[eid]; for(auto i : G[v]){ if(r){ int cost_1 = vis[i][1] ? INT64_MAX : dis + p[i]; int cost_2 = vis[i][0] ? INT64_MAX : dis + min(getM(v, c[i]) - p[i] - (c[i] == c[eid] && (eid - i) % m != 0 ? p[eid] : 0), p[i]); if(cost_1 < d[i][1]){ d[i][1] = cost_1; pq.push({d[i][1], {i, 1}}); } if(cost_2 < d[i][0]){ d[i][0] = cost_2; pq.push({d[i][0], {i, 0}}); } }else{ int cost_1 = vis[i][1] ? INT64_MAX : dis + p[i]; int cost_2 = vis[i][0] ? INT64_MAX : dis + min(getM(v, c[i]) - p[i], p[i]); if(cost_1 < d[i][1]){ d[i][1] = cost_1; pq.push({d[i][1], {i, 1}}); } if(cost_2 < d[i][0]){ d[i][0] = cost_2; pq.push({d[i][0], {i, 0}}); } } } } int ans = INT64_MAX; for(int i = 0; i <= m * 2; i++){ if(b[i] == n){ ans = min(ans, d[i][0]); ans = min(ans, d[i][1]); } } cout << (ans >= (1LL << 60) ? -1 : ans) << endl; }

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:50:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   50 |   for(auto j : gc[i]) cout << j << ' '; cout << endl;
      |   ^~~
Main.cpp:50:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   50 |   for(auto j : gc[i]) cout << j << ' '; cout << endl;
      |                                         ^~~~
Main.cpp:51:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   51 |   for(auto j : s[i]) cout << j << ' '; cout << endl;
      |   ^~~
Main.cpp:51:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   51 |   for(auto j : s[i]) cout << j << ' '; cout << endl;
      |                                        ^~~~
Main.cpp:58:7: warning: unused variable 'u' [-Wunused-variable]
   58 |   int u = a[eid], v = b[eid];
      |       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...