Cod sursa(job #2481112)

Utilizator alexmisto342Turdean Alexandru alexmisto342 Data 26 octombrie 2019 14:10:07
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define ss short
#define x first
#define y second
#define pp pair<int,int>
using namespace std;
int i,j,n,m,total,k,a,b,c,d,op,maxi,modu=1000000007,mini,mij,ls,ld,ul,x,y,im,timp;
set <pp> toti;
vector<int> v[200005];
int l[200005],maxim[200005];
set<pp> :: iterator it;
int main()
{
#ifndef ONLINE_JUDGE
    ifstream cin(".in");
   /// ofstream cout(".out");
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(i = 1; i <= n; i++)
    {
        cin >> a >> b;
        v[a].push_back(b);
        maxim[a] = max(maxim[a],b);
    }
    for(i = 1; i <= n;i++)
    {
        if(maxim[i])
            toti.insert({maxim[i], i});
    }

    cin >> m;
    for(j = 1; j <= m; j++)
    {
        cin >> n;
        for(i = 1; i <= n; i++)
        {
            cin >> l[i];
            if(maxim[ l[i] ])
                toti.erase({maxim[ l[i] ], l[i]});
            else
                i--,n--;
        }

        if(toti.empty())
            cout<<0<<" "<<0<<'\n';
        else
        if(toti.size() == 1)
            cout<<toti.begin()->y<<" "<<*v[ toti.begin()->y].begin()<<'\n';
        else
        {
            it = toti.end();
            it--;
            it--;
            a = v[it->y][ v[it->y].size()-1 ];
            it++;
            a = *lower_bound(v[it->y].begin(), v[it->y].end(), a);
            cout<<it->y<<" "<<a<<'\n';
        }
        for(i = 1; i <= n; i++)
            if(maxim[ l[i] ])
                toti.insert({maxim[ l[i] ], l[i]});

    }
    return 0;
}