oj.uz

Submission #429715

# Submission time Handle Problem Language Result Execution time Memory
429715 2021-06-16T08:54:35 Z 반딧불(#7598) Power plants (CPSPC17_power) C++17
0 / 100
 3 ms 2636 KB 
#include <bits/stdc++.h>
#define SQR(x) ((x)*(x))

using namespace std;

typedef long long ll;

struct Point{
    ll x, y; int idx;
    Point(){}
    Point(ll x, ll y, int idx): x(x), y(y), idx(idx){}

    ll dist(Point &r)const{
        return (x - r.x) * (x - r.x) + (y - r.y) * (y - r.y);
    }
};

bool cmp_x(Point &x, Point &y){
    if(x.x != y.x) return x.x < y.x;
    return x.y < y.y;
}

bool cmp_y(Point &x, Point &y){
    if(x.y != y.y) return x.y < y.y;
    return x.x < y.x;
}

Point cand[7];
void update(Point newC, Point &x){
    if(cand[6].dist(x) <= newC.dist(x)) return;
    swap(cand[6], newC);
    for(int j=6; j>=1; j--){
        if(cand[j].dist(x) < cand[j-1].dist(x)) swap(cand[j], cand[j-1]);
        else break;
    }
}

struct Node{
    Point mid;
    Node *l, *r;
    bool mode; /// 0: x ���� ����, 1: y ���� ����

    Node(vector<Point> vec, bool _m){
        mode = _m;
        if(mode == 0){
            sort(vec.begin(), vec.end(), cmp_x);
        }
        else{
            sort(vec.begin(), vec.end(), cmp_y);
        }

        int s = (int)vec.size();
        mid = vec[s/2];

        vector<Point> lv (vec.begin(), vec.begin() + (s/2));
        vector<Point> rv (vec.begin() + (s/2) + 1, vec.end());

        l = r = nullptr;
        if(!lv.empty()){
            l = new Node(lv, !_m);
        }
        if(!rv.empty()){
            r = new Node(rv, !_m);
        }
    }

    ~Node(){
        if(l) delete l;
        if(r) delete r;
    }

    void findCand(Point x){
        if(!l && !r){
            update(mid, x);
            return;
        }

        if(mode == 0){ /// x �������� ����������.
            if(cmp_x(x, mid)){
                update(mid, x);
                if(l) l->findCand(x);
                if(SQR(x.x - mid.x) <= cand[3].dist(x) && r) r->findCand(x);
            }
            else{
                update(mid, x);
                if(r) r->findCand(x);
                if(SQR(x.x - mid.x) <= cand[3].dist(x) && l) l->findCand(x);
            }
        }
        else{
            if(cmp_y(x, mid)){
                update(mid, x);
                if(l) l->findCand(x);
                if(SQR(x.y - mid.y) <= cand[3].dist(x) && r) r->findCand(x);
            }
            else{
                update(mid, x);
                if(r) r->findCand(x);
                if(SQR(x.y - mid.y) <= cand[3].dist(x) && l) l->findCand(x);
            }
        }
    }
} *root;

int n;
ll x[100002], y[100002];
Point arr[100002];
vector<pair<int, int> > edge;
vector<int> link[100002];

int col[100002];
bool dfs(int x, int c){
    col[x] = c;
    for(auto y: link[x]){
        if(col[y] == c) return false;
        if(col[y]) continue;
        if(!dfs(y, 3-c)) return false;
    }
    return true;
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld", &x[i], &y[i]);
        arr[i] = Point(x[i], y[i], i);
    }

    vector<Point> pointList;
    for(int i=1; i<=n; i++) pointList.push_back(arr[i]);
    root = new Node(pointList, 0);

    for(int i=1; i<=n; i++){
        cand[0] = cand[1] = cand[2] = cand[3] = cand[4] = cand[5] = cand[6] = Point(-1000000001, -1000000001, -1);
        root->findCand(arr[i]);
        assert(cand[0].idx == i);
        for(int j=1; j<7; j++){
            if(cand[j].idx == -1) continue;
            edge.push_back(make_pair(i, cand[j].idx));
        }
    }

    sort(edge.begin(), edge.end(), [&](pair<int, int> &a, pair<int, int> &b){
        return arr[a.first].dist(arr[a.second]) < arr[b.first].dist(arr[b.second]);
    });

    int MIN = 0, MAX = (int)edge.size()-1, ANS = 0;
    while(MIN <= MAX){
        int MID = (MIN + MAX) /2;
        for(int i=1; i<=n; i++) link[i].clear();
        for(int i=0; i<=MID; i++){
            link[edge[i].first].push_back(edge[i].second);
            link[edge[i].second].push_back(edge[i].first);
        }
        for(int i=1; i<=n; i++) col[i] = 0;

        bool good = 1;
        for(int i=1; i<=n; i++){
            if(col[i]) continue;
            if(!dfs(i, 1)){
                good = 0;
                break;
            }
        }

        if(good){
            ANS = MID;
            MIN = MID+1;
        }
        else MAX = MID-1;
    }

    printf("%lld\n", arr[edge[ANS+1].first].dist(arr[edge[ANS+1].second]));
    vector<int> va, vb;
    for(int i=1; i<=n; i++) if(col[i] == 1) va.push_back(i); else vb.push_back(i);
    printf("%d\n", (int)va.size());
    for(auto x: va) printf("%d ", x);
    puts("");
    printf("%d\n", (int)vb.size());
    for(auto x: vb) printf("%d ", x);
    puts("");

    delete root;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         scanf("%lld %lld", &x[i], &y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Incorrect 3 ms 2636 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Incorrect 3 ms 2636 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Incorrect 3 ms 2636 KB Output isn't correct
5 Halted 0 ms 0 KB -