Submission #995266

#TimeUsernameProblemLanguageResultExecution timeMemory
995266gmroh06철도 요금 (JOI16_ho_t3)C++14
100 / 100
91 ms22868 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; inline void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } const ll INF = 1e18; ll n, m, q; int main() { fastio(); cin >> n >> m >> q; vector<vector<pll>> gr(n); vector<ll> idx(m, q), ans(n, -1), dist(n, INF); vector<ll> fin(q + 1, 0); for (ll i = 0, a, b; i < m; i++) { cin >> a >> b; gr[a - 1].emplace_back(b - 1, i); gr[b - 1].emplace_back(a - 1, i); } for (ll i = 0, k; i < q; i++) { cin >> k; idx[k - 1] = i; } ans[0] = q; dist[0] = 0; queue<ll> qu; qu.emplace(0); while (!qu.empty()) { ll loc = qu.front(); qu.pop(); for (auto& [x, i] : gr[loc]) { if (dist[x] > dist[loc] + 1) { dist[x] = dist[loc] + 1; qu.emplace(x); } if (dist[x] == dist[loc] + 1) { ans[x] = max(ans[x], min(ans[loc], idx[i])); } } } for (auto& x : ans) { fin[x]++; } for (ll i = 0, tmp = fin[0]; i < q; tmp += fin[++i]) { cout << tmp << '\n'; } return 0; }

Compilation message (stderr)

2016_ho_t3.cpp: In function 'int main()':
2016_ho_t3.cpp:49:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |         for (auto& [x, i] : gr[loc]) {
      |                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...