fork download
copy 
  1. // Author: Ujjawal Kumar
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define rep(i,a,n) for (int i=a;i<n;i++)
  5. #define per(i,n,a) for (int i=n;i>=a;i--)
  6. #define pb push_back
  7. #define mp make_pair
  8. #define all(x) (x).begin(),(x).end()
  9. #define fst first
  10. #define snd second
  11. #define SZ(x) ((int)(x).size())
  12. #define endl '\n'
  13. #define TC cerr<<"Time elapsed: "<<1000*clock() /CLOCKS_PER_SEC <<"ms: ";
  14. #define mst(a, b) memset(a, b, sizeof(a)); // b can be 0 or -1 only
  15. #define minv(x) *min_element(all(x));
  16. #define maxv(x) *max_element(all(x));
  17. typedef long long ll;
  18. typedef vector<int>               vi;
  19. typedef vector<ll>                vll;
  20. typedef vector<vi>                vvi;
  21. typedef vector<vll>               vvll;
  22. typedef pair<int,int>              pii;
  23. typedef vector<pii>               vpii;
  24. typedef double db;
  25. const ll MOD=1e9+7;
  26. // swap, reverse(it, it)
  27. // mt19937 mrand(random_device{}());
  28.  
  29. // int rnd(int x) { return mrand() % x;}
  30.  
  31. // static auto _ = []() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); return 0; }();
  32. // #pragma GCC optimize("O3")
  33. // #pragma GCC target("avx2, bmi, bmi2, lzcnt, popcnt")
  34.  
  35. // static const bool __boost = [](){
  36. //     cin.tie(nullptr); 
  37. //     cout.tie(nullptr);
  38. //     return ios_base::sync_with_stdio(false);
  39. // }();
  40.  
  41. vi seg(40000), arr(10000);
  42. vpii segp(4000);
  43.  
  44. void buildSegmentTree(int i, int s, int e) {
  45.     if(s == e) {
  46.         segp[i].first = INT_MIN, segp[i].second = arr[e];
  47.         return;
  48.     }
  49.  
  50.     int mid = (s+e)/2;
  51.     buildSegmentTree(i*2+1, s, mid);
  52.     buildSegmentTree(i*2+2, mid+1, e);
  53.  
  54.     // on Backtracking
  55.     vi fourVal = {segp[i*2+1].first, segp[i*2+2].first,segp[i*2+1].second, segp[i*2+2].second};
  56.     sort(fourVal.begin(), fourVal.end(), greater<int>());
  57.     segp[i].first = fourVal[0];
  58.     segp[i].second = fourVal[1];
  59. }
  60.  
  61.  
  62. // Operator overloads <<, >>
  63. template<typename T1, typename T2> // cin >> pair<T1, T2>
  64. istream& operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); }
  65. template<typename T> // cin >> vector<T>
  66. istream& operator>>(istream &istream, vector<T> &v){for (auto &it : v)cin >> it;return istream;}
  67. template<typename T1, typename T2> // cout << pair<T1, T2>
  68. ostream& operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << " " << p.second); }
  69. template<typename T> // cout << vector<T>
  70. ostream& operator<<(ostream &ostream, const vector<T> &c) { for (auto &it : c) cout << it << " "; return ostream; }
  71.  
  72.  
  73. ll powmod(ll a,ll b) {ll res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
  74. ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
  75.  
  76. const int len=50;
  77. bool prime[len];
  78. vi primeList;
  79. void sieve() {
  80.     mst(prime, 1);
  81.     prime[0] = prime[1] = 0;
  82.     for (int p = 2; p*p <= len; p++)  
  83.         if (prime[p])
  84.             for (int i = p*p; i <= len; i += p)
  85.                 prime[i] = 0;
  86.  
  87.     for(int i = 0; i < len; i++)
  88.         if(prime[i])
  89.             primeList.pb(i);
  90. }
  91.  
  92. bool bfs(vi adj[], vi &vis, int city, int power) {
  93.     if(vis[city] != 0) return false;
  94.     vis[city] = 1;
  95.  
  96.     if(power == 0) return true;
  97.  
  98.     queue<int> q;
  99.     q.push(city);
  100.     int level = 1;
  101.  
  102.     while(q.size()) {
  103.         int levelSize = q.size();
  104.  
  105.         for(int i = 0; i < levelSize; i++) {
  106.             int node = q.front(); q.pop();
  107.  
  108.             for(int neighbor: adj[node]) {
  109.                 if(vis[neighbor] == 0) {
  110.                     q.push(neighbor);
  111.                 } else {
  112.                     return false;
  113.                 }
  114.             }
  115.         }
  116.  
  117.         if(++level > power) {
  118.             return true;
  119.         }
  120.     }
  121.     return true;
  122. }
  123.  
  124. void solve(int t) {
  125.     int n, r, m;
  126.     cin >> n >> r >> m;
  127.  
  128.     vi adj[n+1];
  129.     vi vis(n+1, 0);
  130.  
  131.     rep(i, 0, r) {
  132.         int a, b;
  133.         cin >> a >> b;
  134.         adj[a].pb(b);
  135.         adj[b].pb(a);
  136.     }
  137.  
  138.     vpii cityPower;
  139.  
  140.     rep(i, 0, m) {
  141.         int a, b;
  142.         cin >> a >> b;
  143.         cityPower.pb({a, b});
  144.     }
  145.  
  146.     rep(i, 0, m) {
  147.        if(!bfs(adj, vis, cityPower[i].first, cityPower[i].second)) {
  148.         cout << "No" << endl;
  149.         return;
  150.        }
  151.     }
  152.     cout << "Yes" << endl;
  153. }
  154.  
  155.  
  156. int main() {
  157.     // #ifndef ONLINE_JUDGE
  158.     //     freopen("input.txt", "r", stdin);
  159.     //     freopen("output.txt", "w", stdout);
  160.     // #endif
  161.     ios_base::sync_with_stdio(false);  
  162.     cin.tie(NULL);
  163.  
  164.     int t = 1;
  165.     cin >> t;
  166.     while(t--) {
  167.         solve(t+1);
  168.         // cout << '\n';
  169.     }
  170.     // TC;
  171.     return 0;
  172. }
  173.  
Success #stdin #stdout 0.01s 5284KB
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/tx6ViO
language:
C++14 (gcc 8.3)
created:
3 days 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!