rafid_shad

Visiting island

Dec 1st, 2020 (edited)
756
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. ///--------------------------------------data type--------------------------------------------------//
  6. typedef long long int lli;
  7.  
  8. ///----------------------------------------pair------------------------------------------------------//
  9. typedef pair <int, int> pii;
  10.  
  11. ///---------------------------------------dequeue-----------------------------------------------------//
  12. typedef deque <int> DI;
  13. typedef deque <char> DC;
  14.  
  15. ///----------------------------------------stack-----------------------------------------------------//
  16. typedef stack <int> STI;
  17. typedef stack <char> STC;
  18. typedef stack <string> STS;
  19.  
  20. ///---------------------------------------set------------------------------------------------------//
  21. typedef set <int> SI;
  22. typedef set <string> SS;
  23. typedef set <char> SC;
  24. typedef multiset <int> MSI;
  25.  
  26. ///----------------------------------------vector------------------------------------------------------//
  27. typedef vector <int> VI;
  28. typedef vector <char> VC;
  29. typedef vector <string> VS;
  30. typedef vector <lli> VLLI;
  31. typedef vector <pii> VPI;
  32.  
  33. ///----------------------------------------map------------------------------------------------------//
  34. typedef map <int, int> MP;
  35. typedef map <string, int> MPSI;
  36. typedef map <char, int> MPCI;
  37.  
  38. ///----------------------------------------queue------------------------------------------------------//
  39. typedef queue <int> QI;
  40. typedef queue <char> QC;
  41. typedef queue <string> QS;
  42. typedef priority_queue <int> PQI;
  43.  
  44. ///----------------------------------------constant------------------------------------------//
  45.  
  46. #define MAX                 1E9 + 5
  47. #define MIN                 -1E9 - 5
  48. #define INF                 1E18 + 5
  49. #define MOD                 10000007
  50. #define py                  acos(-1.0) /// 3.1415926535897932
  51.  
  52. ///---------------------------------------------------------------------------//
  53.  
  54. #define mk                  make_pair
  55. #define ff                  first
  56. #define ss                  second
  57.  
  58. #define pf                  push_front
  59. #define pb                  push_back
  60. #define popb                pop_back
  61. #define popf                pop_front
  62.  
  63. #define ub                  upper_bound
  64. #define lb                  lower_bound
  65.  
  66. #define itr                 iterator
  67. #define ritr                reverse_iterator
  68.  
  69. ///---------------------------------------------------------------------------//
  70.  
  71.  
  72. ///-----------------------------------------------------------------------------//
  73. #define sq(a)               (a) * (a)
  74. #define SZ(a)               (int) a.size()
  75. #define all(a)              (a).begin(), (a).end()
  76. #define rall(a)             (a).rbegin(), (a).rend()
  77.  
  78. #define rev(v)              reverse( all(v))
  79. #define sortV(v)            sort( all(v))
  80. #define sortA(a,n)          sort(a, a+n)
  81. #define mem(x, y)           memset(x, y, sizeof(x))
  82. #define unq(v)              v.erase( unique( all(v)), v.end())
  83.  
  84. #define to_int(s)           stoi(s)
  85. #define to_upper(s)         transform( s.begin(), s.end(), s.begin(), ::toupper)
  86. #define to_lower(s)         transform( s.begin(), s.end(), s.begin(), ::tolower)
  87.  
  88. ///--------------------------------------------------------------------------------//
  89. #define Erase(V,I)          (V).erase((V).begin()+I)
  90. #define Insert(V,I,M)       (V).insert((V).begin()+I,M)
  91.  
  92. #define read()              freopen("input.txt", "r", stdin)
  93. #define write()             freopen("output.txt", "w", stdout)
  94.  
  95. ///-------------------------------------------------------------------------------------------------------------------------------//
  96. #define loop(i, n)          for(int i = 0; i < n; i++)
  97. #define loops(i, x, n)      for(int i = x; i < n; i++)
  98. #define loopr(i, n)         for(int i = n-1; i >= 0; i--)
  99. #define loopt(i, n)         for(int i = 1; i <= n; i++)
  100.  
  101. ///--------------------------------------------------Debugging-----------------------------------------------------------------
  102.  
  103. //------------------------------------------------------------------------------------------------------------------------------
  104.  
  105.  
  106. ///-----------------------------------template------------------------------------------------//
  107. const int N = 20004;
  108. int n, m, q;
  109. VPI v;
  110. VI graph[N];
  111. int vis[N], vis2[N];
  112. int seg[4*N];
  113.  
  114. int dfs(int v, int p = 0){
  115.     int ans = 0;
  116.     for(auto u : graph[v]){
  117.         if(u == p) continue;
  118.         ans += dfs(u, v);
  119.     }
  120.     return ++ans;
  121. }
  122.  
  123. int bfs(int src){
  124.  
  125.     queue <int> q;
  126.     vis[src] = 1;
  127.     q.push(src);
  128.  
  129.     int last = src;
  130.  
  131.     while(!q.empty()){
  132.         int v = q.front();
  133.         q.pop();
  134.  
  135.         for(auto u : graph[v]){
  136.             if(vis[u]) continue;
  137.             vis[u] = vis[v] + 1;
  138.             last = u;
  139.             q.push(u);
  140.         }
  141.     }
  142.     int diam = 0;
  143.  
  144.     q.push(last);
  145.     vis2[last] = 1;
  146.     while(!q.empty()){
  147.         int v = q.front();
  148.         q.pop();
  149.  
  150.         diam = max(diam, vis2[v]);
  151.         for(auto u : graph[v]){
  152.             if(vis2[u]) continue;
  153.             vis2[u] = vis2[v] + 1;
  154.             q.push(u);
  155.         }
  156.     }
  157.     return diam;
  158.  
  159. }
  160.  
  161. void init(int node, int st, int ed){
  162.     if(st == ed){
  163.        seg[node] = v[st].ss;
  164.        return;
  165.     }
  166.     int md = (st + ed) / 2;
  167.     int lft = node * 2;
  168.     int rgt = lft + 1;
  169.  
  170.     init(lft, st, md);
  171.     init(rgt, md+1, ed);
  172.  
  173.     seg[node] = max( seg[lft], seg[rgt]);
  174.  
  175. }
  176.  
  177. int query(int node, int st, int ed, int l, int r){
  178.  
  179.     int md = (st + ed) / 2; int lft = node * 2; int rgt = node * 2 + 1;
  180.  
  181.     if(st > r or ed < l){
  182.         return -1;
  183.     }
  184.     if(st >= l and ed <= r){
  185.         return seg[node];
  186.     }
  187.     return max (query(lft, st, md, l, r) , query(rgt, md+1, ed, l, r));
  188. }
  189.  
  190. int main()
  191. {
  192.     #ifndef ONLINE_JUDGE
  193.    // read();
  194.     #endif // ONLINE_JUDGE
  195.    // fastIO;
  196.    int t;
  197.    cin >> t;
  198.    int ts = 0;
  199.    while(t--){
  200.  
  201.         cin >> n >> m;
  202.         loopt(i, n){
  203.             graph[i].clear();
  204.         }
  205.         v.clear();
  206.  
  207.         loop(i, m){
  208.             int a, b;
  209.             cin >> a >> b;
  210.             graph[a].pb(a);
  211.             graph[b].pb(b);
  212.         }
  213.  
  214.         memset(vis, 0, sizeof vis);
  215.         memset(vis2, 0, sizeof vis2);
  216.  
  217.         int maxd = 0;
  218.         int maxs = 0;
  219.  
  220.         loopt(i, n){
  221.             if(vis[i]) continue;
  222.  
  223.             int sub = dfs(i);
  224.             int diam = bfs(i);
  225.             maxs = max(maxs, sub);
  226.             maxd = max(maxd, diam);
  227.             v.pb( pii(sub, diam));
  228.         }
  229.  
  230.         sort(all(v));
  231.  
  232.         init(1, 0, v.size()-1);
  233.  
  234.         cout << "Case " << ++ts << ":"<< endl;
  235.  
  236.         cin >> q;
  237.        // no;
  238.         while(q--){
  239.              //   yes;
  240.             int k;
  241.             cout << "input  ";
  242.             cin >> k;
  243.             cout << "k " << k << endl;
  244.             if(k > maxs) cout << "Impossible" << endl;
  245.             else if(k <= maxd) cout << k-1 << endl;
  246.             else{
  247.                 int x =  lb(v.begin(), v.end(), pii(k, 0)) - v.begin();
  248.                 int diam = query( 1, 0, v.size()-1, x, v.size()-1);
  249.                 cout << "Diam " << diam << endl;
  250.                 cout <<  diam + (k-diam)*2 - 1  << endl;
  251.  
  252.             }
  253.  
  254.         }
  255.  
  256.    }
  257.  
  258. }
  259.  
  260.  
  261.  
RAW Paste Data