oj.uz

Submission #429539

# Submission time Handle Problem Language Result Execution time Memory
429539 2021-06-16T05:46:10 Z 반딧불(#7598) Power plants (CPSPC17_power) C++17
35 / 100
 351 ms 33360 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{
        return dist<r.dist;
    }
};

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

int pcol[2002];
int col[2002];
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++){
        for(int j=i+1; j<=n; j++){
            vec.push_back(dat(i, j, (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[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:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%lld %lld", &x[i], &y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 508 KB Output is correct
9 Correct 1 ms 460 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 508 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 266 ms 33308 KB Output is correct
11 Correct 216 ms 33360 KB Output is correct
12 Correct 235 ms 33300 KB Output is correct
13 Correct 227 ms 33304 KB Output is correct
14 Correct 314 ms 33276 KB Output is correct
15 Correct 328 ms 33244 KB Output is correct
16 Correct 276 ms 33320 KB Output is correct
17 Correct 270 ms 33312 KB Output is correct
18 Correct 351 ms 33284 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 508 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 266 ms 33308 KB Output is correct
11 Correct 216 ms 33360 KB Output is correct
12 Correct 235 ms 33300 KB Output is correct
13 Correct 227 ms 33304 KB Output is correct
14 Correct 314 ms 33276 KB Output is correct
15 Correct 328 ms 33244 KB Output is correct
16 Correct 276 ms 33320 KB Output is correct
17 Correct 270 ms 33312 KB Output is correct
18 Correct 351 ms 33284 KB Output is correct
19 Runtime error 2 ms 460 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -