oj.uz

Submission #429536

# Submission time Handle Problem Language Result Execution time Memory
429536 2021-06-16T05:44:17 Z 최서현(#7502) Power plants (CPSPC17_power) C++17
0 / 100
 1 ms 204 KB 
#include <iostream>
#include <vector>
#define pii pair<int, int>
#define ff first
#define ss second

using namespace std;

int n;
pii A[101010];
int col[101010];

bool dfs(int x, long long d, int c)
{
    if(col[x] == c) return true;
    if(col[x] == 3 - c) return false;
    col[x] = c;
    int cnt = 0;
    for(int i = 0; i < n; ++i) if(i != x && 1ll * (A[x].ff - A[i].ff) * (A[x].ff - A[i].ff)
                                            + 1ll * (A[x].ss - A[i].ss) * (A[x].ss - A[i].ss) <= d)
    {
        ++cnt;
//        if(!dfs(i, d, 3 - c)) return false;
    }
    if(cnt > 9) return false;
    for(int i = 0; i < n; ++i) if(i != x && 1ll * (A[x].ff - A[i].ff) * (A[x].ff - A[i].ff)
                                            + 1ll * (A[x].ss - A[i].ss) * (A[x].ss - A[i].ss) <= d)
    {
        ++cnt;
//        if(!dfs(i, d, 3 - c)) return false;
    }

    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for(int i = 0; i < n; ++i) cin >> A[i].ff >> A[i].ss;

    long long s = 0, e = (long long)8e18 + 100;
    while(s + 1 < e)
    {
        long long mid = s + e >> 1;
        for(int i = 0; i < n; ++i) col[i] = 0;
        bool flag = true;
        for(int i = 0; i < n; ++i) if(!col[i])
        {
            if(!dfs(i, mid, 1)) {flag = false; break;}
        }
        if(flag) s = mid;
        else e = mid;
    }

    for(int i = 0; i < n; ++i) col[i] = 0;
    for(int i = 0; i < n; ++i) if(!col[i]) dfs(i, s, 1);
    vector<int> A, B;
    for(int i = 0; i < n; ++i)
    {
        if(col[i] == 1) A.push_back(i);
        else B.push_back(i);
    }

    cout << e << '\n';
    cout << A.size() << '\n';
    for(auto i : A) cout << i + 1 << ' '; cout << '\n';
    cout << B.size() << '\n';
    for(auto i : B) cout << i + 1 << ' '; cout << '\n';
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:47:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         long long mid = s + e >> 1;
      |                         ~~^~~
Main.cpp:69:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   69 |     for(auto i : A) cout << i + 1 << ' '; cout << '\n';
      |     ^~~
Main.cpp:69:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   69 |     for(auto i : A) cout << i + 1 << ' '; cout << '\n';
      |                                           ^~~~
Main.cpp:71:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   71 |     for(auto i : B) cout << i + 1 << ' '; cout << '\n';
      |     ^~~
Main.cpp:71:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   71 |     for(auto i : B) cout << i + 1 << ' '; cout << '\n';
      |                                           ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -