oj.uz

Submission #429606

# Submission time Handle Problem Language Result Execution time Memory
429606 2021-06-16T07:41:12 Z 조영욱(#7653) Power plants (CPSPC17_power) C++17
35 / 100
 6000 ms 31812 KB 
#include <bits/stdc++.h>
using namespace std;

long long dist[2000][2000];
int n;
typedef pair<long long,long long> P;
P arr[2000];
bool vis[2000][2];

bool isp(long long k) {
    memset(vis,0,sizeof(vis));
    for(int v=0;v<n;v++) {
        if (vis[v][0]||vis[v][1]) {
            continue;
        }
        queue<P> q;
        q.push(P(v,0));
        vis[v][0]=true;
        while (!q.empty()) {
            P now=q.front();
            q.pop();
            for(int i=0;i<n;i++) {
                if (i!=now.first&&dist[now.first][i]<k&&!vis[i][1-now.second]) {
                    vis[i][1-now.second]=true;
                    q.push(P(i,1-now.second));
                }
            }
        }
    }
    for(int i=0;i<n;i++) {
        if (vis[i][0]&&vis[i][1]) {
            return false;
        }
    }
    return true;
}

int main(void) {
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%lld %lld",&arr[i].first,&arr[i].second);
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            dist[i][j]=(arr[i].first-arr[j].first)*(arr[i].first-arr[j].first)+(arr[i].second-arr[j].second)*(arr[i].second-arr[j].second);
        }
    }
    long long lo=0; //possible
    long long hi=3e18; //impossible
    while (lo+1<hi) {
        long long mid=(lo+hi)/2;
        if (isp(mid)){
            lo=mid;
        }
        else {
            hi=mid;
        }
    }
    printf("%lld\n",lo);
    isp(lo);
    int cnt=0;
    for(int i=0;i<n;i++) {
        if (vis[i][0]) {
            cnt++;
        }
    }
    printf("%d\n",cnt);
    for(int i=0;i<n;i++) {
        if (vis[i][0]) {
            printf("%d ",i+1);
        }
    }
    printf("\n%d\n",n-cnt);
    for(int i=0;i<n;i++) {
        if (vis[i][1]) {
            printf("%d ",i+1);
        }
    }
}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 KB Output is correct
2 Correct 3 ms 744 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 3 ms 716 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 677 ms 31680 KB Output is correct
11 Correct 642 ms 28772 KB Output is correct
12 Correct 721 ms 29812 KB Output is correct
13 Correct 731 ms 31624 KB Output is correct
14 Correct 827 ms 31668 KB Output is correct
15 Correct 793 ms 30688 KB Output is correct
16 Correct 691 ms 31560 KB Output is correct
17 Correct 729 ms 31812 KB Output is correct
18 Correct 845 ms 31692 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 716 KB Output is correct
2 Correct 3 ms 744 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 3 ms 716 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 677 ms 31680 KB Output is correct
11 Correct 642 ms 28772 KB Output is correct
12 Correct 721 ms 29812 KB Output is correct
13 Correct 731 ms 31624 KB Output is correct
14 Correct 827 ms 31668 KB Output is correct
15 Correct 793 ms 30688 KB Output is correct
16 Correct 691 ms 31560 KB Output is correct
17 Correct 729 ms 31812 KB Output is correct
18 Correct 845 ms 31692 KB Output is correct
19 Execution timed out 6042 ms 1800 KB Time limit exceeded
20 Halted 0 ms 0 KB -