oj.uz

Submission #429538

# Submission time Handle Problem Language Result Execution time Memory
429538 2021-06-16T05:45:18 Z 최서현(#7502) Power plants (CPSPC17_power) C++17
35 / 100
 6000 ms 1464 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
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 182 ms 332 KB Output is correct
11 Correct 97 ms 332 KB Output is correct
12 Correct 66 ms 456 KB Output is correct
13 Correct 100 ms 368 KB Output is correct
14 Correct 217 ms 460 KB Output is correct
15 Correct 36 ms 332 KB Output is correct
16 Correct 171 ms 332 KB Output is correct
17 Correct 199 ms 332 KB Output is correct
18 Correct 203 ms 436 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 182 ms 332 KB Output is correct
11 Correct 97 ms 332 KB Output is correct
12 Correct 66 ms 456 KB Output is correct
13 Correct 100 ms 368 KB Output is correct
14 Correct 217 ms 460 KB Output is correct
15 Correct 36 ms 332 KB Output is correct
16 Correct 171 ms 332 KB Output is correct
17 Correct 199 ms 332 KB Output is correct
18 Correct 203 ms 436 KB Output is correct
19 Execution timed out 6077 ms 1464 KB Time limit exceeded
20 Halted 0 ms 0 KB -