Submission #365322

#TimeUsernameProblemLanguageResultExecution timeMemory
365322GioChkhaidze철도 요금 (JOI16_ho_t3)C++14
100 / 100
218 ms26092 KiB
#include <bits/stdc++.h> #define pb push_back #define F first #define S second using namespace std; const int N = 2e5 + 5; int n, m, q, ans; int in[N], d[N], a[N], b[N]; bool act[N], ed[N], used[N]; vector < pair < int , int > > v[N], g[N]; queue < int > qr; void lazy(int x, int idx) { --in[x]; ed[idx] = true; if (!in[x]) { ++ans; for (int i = 0; i < g[x].size(); ++i) { int to = g[x][i].F, id = g[x][i].S; if (ed[id]) continue; lazy(to, id); } } } main () { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m >> q; for (int i = 1; i <= m; ++i) { cin >> a[i] >> b[i]; v[a[i]].pb({b[i], i}); v[b[i]].pb({a[i], i}); } for (int i = 2; i <= n; ++i) { d[i] = 1e9; } qr.push(1); while (!qr.empty()) { int x = qr.front(); qr.pop(); for (int i = 0; i < v[x].size(); ++i) { int to = v[x][i].F, id = v[x][i].S; if (d[x] + 1 < d[to]) { d[to] = d[x] + 1; qr.push(to); } if (d[x] + 1 == d[to]) { g[x].pb({to, id}); act[id] = true; ++in[to]; } } } for (int i = 1; i <= m; ++i) { if (d[a[i]] > d[b[i]]) swap(a[i], b[i]); } for (int i = 1; i <= q; ++i) { int x; cin >> x; if (act[x] && !ed[x]) { lazy(b[x], x); } cout << ans << "\n"; } }

Compilation message (stderr)

2016_ho_t3.cpp: In function 'void lazy(int, int)':
2016_ho_t3.cpp:22:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for (int i = 0; i < g[x].size(); ++i) {
      |                   ~~^~~~~~~~~~~~~
2016_ho_t3.cpp: At global scope:
2016_ho_t3.cpp:30:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main () {
      |       ^
2016_ho_t3.cpp: In function 'int main()':
2016_ho_t3.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int i = 0; i < v[x].size(); ++i) {
      |                   ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...