oj.uz

답안 #429600

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
429600 2021-06-16T07:34:10 Z 조영욱(#7653) Power plants (CPSPC17_power) C++17
0 / 100
 3 ms 716 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",lo);
}

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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 716 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 716 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 716 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -