4098 2023. 03. 14 13:33:22 1478 MobilNet (50 pont) cpp17 Elfogadva 50/50 119ms 15112 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 Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1812 KiB
2 Elfogadva 0/0 10ms 3068 KiB
3 Elfogadva 2/2 3ms 2320 KiB
4 Elfogadva 2/2 3ms 2536 KiB
5 Elfogadva 2/2 3ms 2664 KiB
6 Elfogadva 2/2 3ms 2776 KiB
7 Elfogadva 2/2 3ms 2788 KiB
8 Elfogadva 2/2 4ms 3228 KiB
9 Elfogadva 2/2 4ms 3592 KiB
10 Elfogadva 2/2 7ms 3876 KiB
11 Elfogadva 2/2 8ms 4260 KiB
12 Elfogadva 2/2 13ms 4540 KiB
13 Elfogadva 3/3 19ms 6084 KiB
14 Elfogadva 3/3 32ms 7264 KiB
15 Elfogadva 3/3 39ms 8356 KiB
16 Elfogadva 3/3 48ms 9524 KiB
17 Elfogadva 3/3 64ms 11360 KiB
18 Elfogadva 3/3 71ms 11700 KiB
19 Elfogadva 3/3 81ms 13744 KiB
20 Elfogadva 3/3 119ms 15112 KiB
21 Elfogadva 3/3 104ms 14816 KiB
22 Elfogadva 3/3 92ms 14252 KiB