Visiting island LightOJ

#include<bits/stdc++.h>
using namespace std;


///--------------------------------------data type--------------------------------------------------//
typedef long long int lli;

///----------------------------------------pair------------------------------------------------------//
typedef pair <int, int> pii;

///---------------------------------------dequeue-----------------------------------------------------//
typedef deque <int> DI;
typedef deque <char> DC;

///----------------------------------------stack-----------------------------------------------------//
typedef stack <int> STI;
typedef stack <char> STC;
typedef stack <string> STS;

///---------------------------------------set------------------------------------------------------//
typedef set <int> SI;
typedef set <string> SS;
typedef set <char> SC;
typedef multiset <int> MSI;

///----------------------------------------vector------------------------------------------------------//
typedef vector <int> VI;
typedef vector <char> VC;
typedef vector <string> VS;
typedef vector <lli> VLLI;
typedef vector <pii> VPI;

///----------------------------------------map------------------------------------------------------//
typedef map <int, int> MP;
typedef map <string, int> MPSI;
typedef map <char, int> MPCI;

///----------------------------------------queue------------------------------------------------------//
typedef queue <int> QI;
typedef queue <char> QC;
typedef queue <string> QS;
typedef priority_queue <int> PQI;

///----------------------------------------constant------------------------------------------//

#define MAX                 1E9 + 5
#define MIN                 -1E9 - 5
#define INF                 1E18 + 5
#define MOD                 10000007
#define py                  acos(-1.0) /// 3.1415926535897932

///---------------------------------------------------------------------------//

#define mk                  make_pair
#define ff                  first
#define ss                  second

#define pf                  push_front
#define pb                  push_back
#define popb                pop_back
#define popf                pop_front

#define ub                  upper_bound
#define lb                  lower_bound

#define itr                 iterator
#define ritr                reverse_iterator

///---------------------------------------------------------------------------//


///-----------------------------------------------------------------------------//
#define sq(a)               (a) * (a)
#define SZ(a)               (int) a.size()
#define all(a)              (a).begin(), (a).end()
#define rall(a)             (a).rbegin(), (a).rend()

#define rev(v)              reverse( all(v))
#define sortV(v)            sort( all(v))
#define sortA(a,n)          sort(a, a+n)
#define mem(x, y)           memset(x, y, sizeof(x))
#define unq(v)              v.erase( unique( all(v)), v.end())

#define to_int(s)           stoi(s)
#define to_upper(s)         transform( s.begin(), s.end(), s.begin(), ::toupper)
#define to_lower(s)         transform( s.begin(), s.end(), s.begin(), ::tolower)

///--------------------------------------------------------------------------------//
#define Erase(V,I)          (V).erase((V).begin()+I)
#define Insert(V,I,M)       (V).insert((V).begin()+I,M)

#define read()              freopen("input.txt", "r", stdin)
#define write()             freopen("output.txt", "w", stdout)

///-------------------------------------------------------------------------------------------------------------------------------//
#define loop(i, n)          for(int i = 0; i < n; i++)
#define loops(i, x, n)      for(int i = x; i < n; i++)
#define loopr(i, n)         for(int i = n-1; i >= 0; i--)
#define loopt(i, n)         for(int i = 1; i <= n; i++)

///--------------------------------------------------Debugging-----------------------------------------------------------------

//------------------------------------------------------------------------------------------------------------------------------


///-----------------------------------template------------------------------------------------//
const int N = 20004;
int n, m, q;
VPI v;
VI graph[N];
int vis[N], vis2[N];
int seg[4*N];

int dfs(int v, int p = 0){
    int ans = 0;
    for(auto u : graph[v]){
        if(u == p) continue;
        ans += dfs(u, v);
    }
    return ++ans;
}

int bfs(int src){

    queue <int> q;
    vis[src] = 1;
    q.push(src);

    int last = src;

    while(!q.empty()){
        int v = q.front();
        q.pop();

        for(auto u : graph[v]){
            if(vis[u]) continue;
            vis[u] = vis[v] + 1;
            last = u;
            q.push(u);
        }
    }
    int diam = 0;

    q.push(last);
    vis2[last] = 1;
    while(!q.empty()){
        int v = q.front();
        q.pop();

        diam = max(diam, vis2[v]);
        for(auto u : graph[v]){
            if(vis2[u]) continue;
            vis2[u] = vis2[v] + 1;
            q.push(u);
        }
    }
    return diam;

}

void init(int node, int st, int ed){
    if(st == ed){
       seg[node] = v[st].ss;
       return;
    }
    int md = (st + ed) / 2;
    int lft = node * 2;
    int rgt = lft + 1;

    init(lft, st, md);
    init(rgt, md+1, ed);

    seg[node] = max( seg[lft], seg[rgt]);

}

int query(int node, int st, int ed, int l, int r){

    int md = (st + ed) / 2; int lft = node * 2; int rgt = node * 2 + 1;

    if(st > r or ed < l){
        return -1;
    }
    if(st >= l and ed <= r){
        return seg[node];
    }
    return max (query(lft, st, md, l, r) , query(rgt, md+1, ed, l, r));
}

int main()
{
    #ifndef ONLINE_JUDGE
   // read();
    #endif // ONLINE_JUDGE
   // fastIO;
   int t;
   cin >> t;
   int ts = 0;
   while(t--){

        cin >> n >> m;
        loopt(i, n){
            graph[i].clear();
        }
        v.clear();

        loop(i, m){
            int a, b;
            cin >> a >> b;
            graph[a].pb(a);
            graph[b].pb(b);
        }

        memset(vis, 0, sizeof vis);
        memset(vis2, 0, sizeof vis2);

        int maxd = 0;
        int maxs = 0;

        loopt(i, n){
            if(vis[i]) continue;

            int sub = dfs(i);
            int diam = bfs(i);
            maxs = max(maxs, sub);
            maxd = max(maxd, diam);
            v.pb( pii(sub, diam));
        }

        sort(all(v));

        init(1, 0, v.size()-1);

        cout << "Case " << ++ts << ":"<< endl;

        cin >> q;
       // no;
        while(q--){
             //   yes;
            int k;
            cout << "input  ";
            cin >> k;
            cout << "k " << k << endl;
            if(k > maxs) cout << "Impossible" << endl;
            else if(k <= maxd) cout << k-1 << endl;
            else{
                int x =  lb(v.begin(), v.end(), pii(k, 0)) - v.begin();
                int diam = query( 1, 0, v.size()-1, x, v.size()-1);
                cout << "Diam " << diam << endl;
                cout <<  diam + (k-diam)*2 - 1  << endl;

            }

        }

   }

}