fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. void solve() {
  6.     int n, r, m;
  7.     bool ok = true;
  8.     cin >> n >> r >> m;
  9.  
  10.     vector<vector<int> > adj(n + 10);
  11.     vector<bool> vis(n + 10, false);
  12.     vector<bool> done(n + 10, false);
  13.     vector<int> dist(n + 10, 0);
  14.     vector<pair<int, int>> soldiers;
  15.  
  16.     while (r--) {
  17.         int u, v;
  18.         cin >> u >> v;
  19.         adj[u].push_back(v);
  20.         adj[v].push_back(u);
  21.     }
  22.     while (m--) {
  23.         int u, v;
  24.         cin >> u >> v;
  25.         soldiers.push_back({u, v});
  26.     }
  27.  
  28.     for (auto it : soldiers) {
  29.         int c = it.first;
  30.         int s = it.second;
  31.  
  32.         queue<int> q;
  33.         q.push(c);
  34.         vis[c] = true; dist[c] = 0;
  35.  
  36.         while (!q.empty()) {
  37.             int cur = q.front();
  38.             q.pop();
  39.             vis[cur] = true;
  40.             if (s < dist[cur]) break;
  41.             if (done[cur]) {
  42.                 ok = false; break;
  43.             }
  44.             for (int v : adj[cur]) {
  45.                 if (!vis[v]) {
  46.                     dist[v] = dist[cur] + 1;
  47.                     if (dist[v] <= s) vis[v] = true;
  48.                     q.push(v);
  49.                 }
  50.             }
  51.             done[cur] = true;
  52.         }
  53.  
  54.         if (!ok) break;
  55.     }
  56.  
  57.     for (int i = 1; i <= n; i++) {
  58.         if (!done[i]) {
  59.             ok = false; break;
  60.         }
  61.     }
  62.  
  63.     cout << (ok ? "YES\n" : "NO\n");
  64. }
  65.  
  66. int main() {
  67.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  68.  
  69.     int T;
  70.     cin >> T;
  71.     while (T--) {
  72.         solve();
  73.     }
  74. }
Success #stdin #stdout 0s 4272KB
comments (?)
stdin
copy 
2
3 2 2
1 2
2 3
1 2
2 0
4 5 2
1 4
1 2
1 3
4 2
3 4
2 1
3 0
stdout
copy 
NO
YES
https://ideone.com/7cGTFC
akbar
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!