oj.uz

Submission #429535

# Submission time Handle Problem Language Result Execution time Memory
429535 2021-06-16T05:43:02 Z 최서현(#7502) Power plants (CPSPC17_power) C++17
35 / 100
 6000 ms 3028 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;
    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)
    {
        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:37:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         long long mid = s + e >> 1;
      |                         ~~^~~
Main.cpp:59:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   59 |     for(auto i : A) cout << i + 1 << ' '; cout << '\n';
      |     ^~~
Main.cpp:59:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   59 |     for(auto i : A) cout << i + 1 << ' '; cout << '\n';
      |                                           ^~~~
Main.cpp:61:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   61 |     for(auto i : B) cout << i + 1 << ' '; cout << '\n';
      |     ^~~
Main.cpp:61:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   61 |     for(auto i : B) cout << i + 1 << ' '; cout << '\n';
      |                                           ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 82 ms 336 KB Output is correct
11 Correct 65 ms 348 KB Output is correct
12 Correct 34 ms 344 KB Output is correct
13 Correct 59 ms 332 KB Output is correct
14 Correct 101 ms 496 KB Output is correct
15 Correct 15 ms 404 KB Output is correct
16 Correct 82 ms 344 KB Output is correct
17 Correct 90 ms 356 KB Output is correct
18 Correct 106 ms 492 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 82 ms 336 KB Output is correct
11 Correct 65 ms 348 KB Output is correct
12 Correct 34 ms 344 KB Output is correct
13 Correct 59 ms 332 KB Output is correct
14 Correct 101 ms 496 KB Output is correct
15 Correct 15 ms 404 KB Output is correct
16 Correct 82 ms 344 KB Output is correct
17 Correct 90 ms 356 KB Output is correct
18 Correct 106 ms 492 KB Output is correct
19 Execution timed out 6089 ms 3028 KB Time limit exceeded
20 Halted 0 ms 0 KB -