fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define y1 hld
  4. #define int long long
  5. #define pii pair<int, int>
  6. #define vi vector<int>
  7. #define vii vector<pii>
  8. #define fi first
  9. #define se second
  10. #define big (int)1e18
  11. #define small (int)1e9
  12. #define mouse (int)-1e18
  13. #define cat (int)-1e9
  14. #define pb push_back
  15. #define eb emplace_back
  16. #define tri pair<int, pair<int, int>>
  17. #define a1 fi
  18. #define a2 se.fi
  19. #define a3 se.se
  20. #define quad pair<pair<int, int>, pair<int, int>>
  21. #define b1 fi.fi
  22. #define b2 fi.se
  23. #define b3 se.fi
  24. #define b4 se.se
  25. #define all(x) x.begin(), x.end()
  26. #define rall(x) x.rbegin(), x.rend()
  27. #define srt(x) sort(all(x));
  28. #define bit(x, i) ((x >> i) & 1)
  29. #define mask(i) (1LL << i)
  30. #define sz(x) (int)x.size()
  31. #define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end())
  32. #define debug(x) cerr << x << ' '
  33. #define debg(x) cerr << x << '\n'
  34. #define deb(x, y) cerr << x << ' ' << y << '\n'
  35. #define de(x, y, z) cerr << x << ' ' << y << ' ' << z << '\n'
  36. #define htbd(x, y, z, t) cerr << x << ' ' << y << ' ' << z << ' ' << t << '\n'
  37. template <class T>
  38. using minheap = priority_queue<T, vector<T>, greater<T>>;
  39. int dx[4] = {1, -1, 0, 0};
  40. int dy[4] = {0, 0, 1, -1};
  41. tri t3(int a, int b, int c) { return {a, {b, c}}; }
  42. quad t4(int a, int b, int c, int d) { return {{a, b}, {c, d}}; }
  43. void ptri(tri x) { cerr << x.a1 << ' ' << x.a2 << ' ' << x.a3 << '\n'; }
  44. void pquad(quad x) {
  45.     cerr << x.b1 << ' ' << x.b2 << ' ' << x.b3 << ' ' << x.b4 << '\n';
  46. }
  47. int ceil_div(int a, int b) { return (a + b - 1) / b; }
  48. #define fill0(x) memset(x, 0, sizeof x)
  49. #define f36(x) memset(x, -1, sizeof x)
  50. #define inf(x) memset(x, 0x3f, sizeof x)
  51. #define nyc(x) memset(x, -0x3f, sizeof x)
  52. #define loop(i, a, b) for (int i = (a); i <= (b); i++)
  53. #define back(i, a, b) for (int i = (a); i >= (b); i--)
  54. #define popcnt(x) __builtin_popcountll(x)
  55. #define lb lower_bound
  56. #define ub upper_bound
  57. #define f59(a, b) a = min(a, b)
  58. #define f69(a, b) a = max(a, b)
  59. #define rep(i, n) for (int i = 1; i <= n; i++)
  60. #define has(x, y) (x.find(y) != x.end())
  61. #define each(x, a) for (auto &x : a)
  62. #define lbit(x) (x & -x)
  63. #define f(u, v) adj[u].push_back(v)
  64. #define g(u, v, w) adj[u].push_back({v, w})
  65. #define f2(u, v) (f(u, v), f(v, u))
  66. #define g2(u, v, w) (g(u, v, w), g(v, u, w))
  67. const int N = 2e5 + 5;
  68. vector<int> adj[N];
  69. int dist[N], p[N];
  70. set<int> s;
  71. signed main() {
  72.     ios_base::sync_with_stdio(0);
  73.     cin.tie(0);
  74.     cout.tie(0);
  75.     if (ifstream("WOTU.INP")) {
  76.         freopen("WOTU.INP", "r", stdin);
  77.         freopen("WOTU.OUT", "w", stdout);
  78.     }
  79.     memset(dist, 0x3f, sizeof dist);
  80.     int n, m, k;
  81.     cin >> n >> m >> k;
  82.     for (int i = 1; i <= m; i++) {
  83.         int U, V;
  84.         cin >> U >> V;
  85.         f(V, U);
  86.     }
  87.     for (int i = 1; i <= n; i++) cin >> p[i];
  88.     queue<int> q;
  89.     q.push(n);
  90.     dist[n] = 0;
  91.     while (q.size()) {
  92.         int u = q.front();
  93.         q.pop();
  94.         for (int v : adj[u])
  95.             if (dist[v] > dist[u] + 1) dist[v] = dist[u] + 1, q.push(v);
  96.     }
  97.     for (int i = 1; i <= n; i++) s.insert(dist[p[i]] + i - 1);
  98.     int x, y;
  99.     while (k--) {
  100.         cin >> x >> y;
  101.         s.erase(s.find(dist[p[x]] + x - 1));
  102.         s.erase(s.find(dist[p[y]] + y - 1));
  103.         s.insert(dist[p[y]] + x - 1);
  104.         s.insert(dist[p[x]] + y - 1);
  105.         swap(p[x], p[y]);
  106.         cout << *s.begin() << '\n';
  107.     }
  108. }
Success #stdin #stdout 0.01s 11136KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OZgebi
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!