fork download
copy 
  1. #include <set>
  2. #include <map>
  3. #include <list>
  4. #include <cmath>
  5. #include <queue>
  6. #include <stack>
  7. #include <cstdio>
  8. #include <string>
  9. #include <vector>
  10. #include <cstdlib>
  11. #include <cstring>
  12. #include <sstream>
  13. #include <iomanip>
  14. #include <complex>
  15. #include <iostream>
  16. #include <algorithm>
  17.  
  18. #include <ctime>
  19. #include <deque>
  20. #include <bitset>
  21. #include <cctype>
  22. #include <utility>
  23. #include <cassert>
  24. using namespace std;
  25.  
  26. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
  27. #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
  28. #define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
  29. #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  30.  
  31. #define DEBUG(x) { cout << #x << " = " << x << endl; }
  32. #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
  33. #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
  34.  
  35. const int MN = 10111;
  36. vector<int> ke[MN];
  37. int d[MN], id[MN];
  38. int important[MN];
  39. int a[MN];
  40. int save[211][MN];
  41.  
  42. void bfs(int u) {
  43.     memset(d, -1, sizeof d);
  44.     queue<int> qu; qu.push(u);
  45.     d[u] = 0;
  46.     while (!qu.empty()) {
  47.         u = qu.front(); qu.pop();
  48.         REP(i,ke[u].size()) {
  49.             int v = ke[u][i];
  50.             if (d[v] < 0) {
  51.                 qu.push(v);
  52.                 d[v] = d[u] + 1;
  53.             }
  54.         }
  55.     }
  56. }
  57.  
  58. int main() {
  59.     ios :: sync_with_stdio(false); cin.tie(NULL);
  60.     cout << (fixed) << setprecision(6);
  61.     int test; cin >> test;
  62.     while (test--) {
  63.         int nz, nr;
  64.         cin >> nz >> nr;
  65.  
  66.         FOR(i,1,9999) ke[i].clear();
  67.         memset(important, false, sizeof important);
  68.  
  69.         FOR(i,1,nz) {
  70.             cin >> id[i];
  71.             int k; cin >> k;
  72.             while (k--) {
  73.                 int u; cin >> u;
  74.                 ke[id[i]].push_back(u);
  75.             }
  76.         }
  77.         FOR(i,1,nr) {
  78.             int k; cin >> k;
  79.             while (k--) {
  80.                 int u; cin >> u;
  81.                 important[u] = true;
  82.             }
  83.         }
  84.         int cnt = 0;
  85.         FOR(i,1,9999)
  86.             if (important[i]) {
  87.                 a[++cnt] = i;
  88.             }
  89.         FOR(i,1,cnt) {
  90.             bfs(a[i]);
  91.             FOR(x,1,nz)
  92.                 save[i][x] = d[id[x]];
  93.         }
  94.         int res = 1000111, u = -1;
  95.         FOR(j,1,nz) {
  96.             int cur = 0;
  97.             FOR(i,1,cnt)
  98.                 cur = max(cur, save[i][j]);
  99.             if (cur < res || (cur == res && id[j] < id[u])) {
  100.                 res = cur;
  101.                 u = j;
  102.             }
  103.         }
  104.         cout << 1 + res << ' ' << id[u] << endl;
  105.     }
  106.     return 0;
  107. }
  108.  
  109.  
Success #stdin #stdout 0s 12088KB
comments (?)
stdin
copy 
1
17 2
7400 6 7401 7402 7403 7404 7405 7406
7401 6 7412 7402 7400 7406 7410 7411
7402 5 7412 7403 7400 7401 7411
7403 6 7413 7414 7404 7400 7402 7412
7404 5 7403 7414 7415 7405 7400
7405 6 7404 7415 7407 7408 7406 7400
7406 7 7400 7405 7407 7408 7409 7410 7401
7407 4 7408 7406 7405 7415
7408 4 7409 7406 7405 7407
7409 3 7410 7406 7408
7410 4 7411 7401 7406 7409
7411 5 7416 7412 7402 7401 7410
7412 6 7416 7411 7401 7402 7403 7413
7413 3 7412 7403 7414
7414 3 7413 7403 7404
7415 3 7404 7405 7407
7416 2 7411 7412
5 7409 7408 7407 7405 7415
6 7415 7404 7414 7413 7412 7416
stdout
copy 
4 7400
https://ideone.com/kOyz0C
language:
C++ (gcc 8.3)
created:
10 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!