oj.uz

Submission #429560

# Submission time Handle Problem Language Result Execution time Memory
429560 2021-06-16T06:40:18 Z 반딧불(#7598) Power plants (CPSPC17_power) C++17
0 / 100
 3 ms 2636 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    int a, b; ll dist;
    dat(){}
    dat(int a, int b, ll dist): a(a), b(b), dist(dist){}
    bool operator<(const dat &r)const{
        if(dist != r.dist || a != r.a) return dist<r.dist;
        return (b - a + 100000000) % 100000000 < (r.b - r.a + 100000000) % 100000000;
    }
};

int n;
ll x[100002], y[100002];
vector<int> link[100002];
vector<dat> vec;

int pcol[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]);
    }
    for(int i=1; i<=n; i++){
        vector<dat> tvec;
        for(int j=1; j<=n; j++){
            if(i==j) continue;
            tvec.push_back(dat(i, j, (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])));
        }
        sort(tvec.begin(), tvec.end());
        for(int j=0; j<(int)tvec.size() && j<2; j++) vec.push_back(tvec[j]);
    }
    sort(vec.begin(), vec.end());

    ll ans = 0;
    for(dat tmp: vec){
        link[tmp.a].push_back(tmp.b);
        link[tmp.b].push_back(tmp.a);

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

    printf("%lld\n", ans);
    vector<int> a, b;
    for(int i=1; i<=n; i++) if(pcol[i] == 1) a.push_back(i); else b.push_back(i);
    printf("%d\n", (int)a.size());
    for(auto x: a) printf("%d ", x);
    puts("");
    printf("%d\n", (int)b.size());
    for(auto x: b) printf("%d ", x);
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 Correct 3 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Incorrect 3 ms 2636 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 Correct 3 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Incorrect 3 ms 2636 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 Correct 3 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Incorrect 3 ms 2636 KB Output isn't correct
7 Halted 0 ms 0 KB -