40982023-03-14 13:33:221478MobilNet (50 pont)cpp17Elfogadva 50/50119ms15112 KiB
#include <bits/stdc++.h>

using namespace std;

struct pont{
    int x, y, ind;
};

struct el{
    int cs, ert;
};

bool xszerint(pont j, pont i){
    if(i.x == j.x) return i.y<j.y;
    else return i.x<j.x;
}

bool yszerint(pont j, pont i){
    if(i.y == j.y) return i.x<j.x;
    else return i.y<j.y;
}

struct CompErt {
    bool operator()(el const& p1, el const& p2)
    {
        // return "true" if "p1" is ordered
        // before "p2", for example:
        return p1.ert > p2.ert;
    }
};

int main()
{
//   ifstream cin("be.txt");
    int n;
    cin>>n;
    vector<pont> a(n+1);
    vector<vector<el>> szlista(n+1);
    for(int i=1; i<=n; i++){
        cin>>a[i].x>>a[i].y;
        a[i].ind = i;
    }
//    for(int i=1; i<=n; i++){
//        cout<<i<<": "<<a[i].x<<" "<<a[i].y<<endl;
//    }
    sort(a.begin()+1, a.end(), xszerint);
    for(int i=1; i<n; i++){
        if(a[i].x == a[i+1].x){
            el seged;
            seged.cs = a[i+1].ind;
            seged.ert = abs(a[i].y - a[i+1].y);
            szlista[a[i].ind].push_back(seged);
            seged.cs = a[i].ind;
            szlista[a[i+1].ind].push_back(seged);
        }
    }
    sort(a.begin()+1, a.end(), yszerint);
    for(int i=1; i<n; i++){
        if(a[i].y == a[i+1].y){
            el seged;
            seged.cs = a[i+1].ind;
            seged.ert = abs(a[i].x - a[i+1].x);
            szlista[a[i].ind].push_back(seged);
            seged.cs = a[i].ind;
            szlista[a[i+1].ind].push_back(seged);
        }
    }
//    for(int i=1; i<=n; i++)
//    {
//        cout<<i<<": ";
//        for(el x:szlista[i]) cout<<x.cs<<" "<<x.ert<<", ";
//        cout<<endl;
//    }
    vector<bool> lattam(n+1);
    lattam[1] = 1;
    int maxhossz = 0;
    int maxhosszdb = 0;

    priority_queue <el, vector<el>, CompErt> pq;

    for(el x: szlista[1]) pq.push(x);

    for(int i=1; i<n; ){
        if(!lattam[pq.top().cs]){
            lattam[pq.top().cs] = 1;
//            cout<<pq.top().cs<<" ";
            if(pq.top().ert > maxhossz){
                maxhosszdb = 1;
                maxhossz = pq.top().ert;
            }
            else if(pq.top().ert == maxhossz){
                maxhosszdb++;
            }
            i++;
            int csucs = pq.top().cs;
            pq.pop();
            for(el x: szlista[csucs]) pq.push(x);
            //cout<<pq.top().cs<<" ";
        }
        //cout<<"*";
        else pq.pop();
    }
    cout<<maxhossz<<'\n'<<maxhosszdb;


    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1812 KiB
2Elfogadva0/010ms3068 KiB
3Elfogadva2/23ms2320 KiB
4Elfogadva2/23ms2536 KiB
5Elfogadva2/23ms2664 KiB
6Elfogadva2/23ms2776 KiB
7Elfogadva2/23ms2788 KiB
8Elfogadva2/24ms3228 KiB
9Elfogadva2/24ms3592 KiB
10Elfogadva2/27ms3876 KiB
11Elfogadva2/28ms4260 KiB
12Elfogadva2/213ms4540 KiB
13Elfogadva3/319ms6084 KiB
14Elfogadva3/332ms7264 KiB
15Elfogadva3/339ms8356 KiB
16Elfogadva3/348ms9524 KiB
17Elfogadva3/364ms11360 KiB
18Elfogadva3/371ms11700 KiB
19Elfogadva3/381ms13744 KiB
20Elfogadva3/3119ms15112 KiB
21Elfogadva3/3104ms14816 KiB
22Elfogadva3/392ms14252 KiB