oj.uz

Submission #429721

# Submission time Handle Problem Language Result Execution time Memory
429721 2021-06-16T08:56:05 Z 장태환(#7566) Power plants (CPSPC17_power) C++17
35 / 100
 1516 ms 32600 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int col[2010];
vector<int>link[2001];
pair<int,int>pos[2001];
int ans;
void dfs(int n,int c)
{
    if(col[n])
    {
        if(c!=col[n])
            ans=0;
        return;
    }
    col[n]=c;
    int i;
    for(i=0;i<link[n].size();i++)
    {
        dfs(link[n][i],3-c);
    }
}
signed main()
{
    int N;
    cin >> N;
    int i;
    for(i=0;i<N;i++)
    {
        cin >> pos[i].first>>pos[i].second;
    }
    if(N==2)
    {
        cout <<(pos[0].first-pos[1].first)*(pos[0].first-pos[1].first)+(pos[0].second-pos[1].second)*(pos[0].second-pos[1].second)<<'\n';
        cout <<1<<'\n'<<1<<'\n'<<1<<'\n'<<2;
        return 0;
    }
    int s=0,e=3LL<<60;
    while(s!=e)
    {
        memset(col,0,sizeof(col));
        int i;
        int m=(s+e+1)/2;
        for(i=0;i<N;i++)
        {
            link[i].clear();
            int j;
            for(j=0;j<N;j++)
            {
                if(j==i)
                continue;
                if((pos[i].first-pos[j].first)*(pos[i].first-pos[j].first)+(pos[i].second-pos[j].second)*(pos[i].second-pos[j].second)<m)
                {
                    link[i].push_back(j);
                }
            }
        }
        ans=1;
        for(i=0;i<N;i++)
        {
            if(!col[i])
            dfs(i,1);
        }

        if(ans)
            s=m;
        else
            e=m-1;
    }
    cout <<s<<'\n';
    memset(col,0,sizeof(col));
    for(i=0;i<N;i++)
    {
            link[i].clear();
            int j;
            for(j=0;j<N;j++)
            {
                if(j==i)
                continue;
                if((pos[i].first-pos[j].first)*(pos[i].first-pos[j].first)+(pos[i].second-pos[j].second)*(pos[i].second-pos[j].second)<s)
                {
                    link[i].push_back(j);
                }
            }
        }
    for(i=0;i<N;i++)
        {
            if(!col[i])
            dfs(i,1);
        }
    vector<int>f,sr;
    for(i=0;i<N;i++)
    {
        if(col[i]==1)
            f.push_back(i+1);
        else
            sr.push_back(i+1);
    }
    cout <<f.size()<<'\n';
    for(i=0;i<f.size();i++)
    {
        cout <<f[i]<<' ';
    }
    cout <<'\n';
    cout <<sr.size()<<'\n';
    for(i=0;i<sr.size();i++)
    {
        cout <<sr[i]<<' ';
    }
}

Compilation message

Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:18:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(i=0;i<link[n].size();i++)
      |             ~^~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:100:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(i=0;i<f.size();i++)
      |             ~^~~~~~~~~
Main.cpp:106:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(i=0;i<sr.size();i++)
      |             ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 460 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 5 ms 440 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 5 ms 460 KB Output is correct
9 Correct 6 ms 456 KB Output is correct
10 Correct 1466 ms 32596 KB Output is correct
11 Correct 1130 ms 29572 KB Output is correct
12 Correct 1321 ms 30628 KB Output is correct
13 Correct 1397 ms 32484 KB Output is correct
14 Correct 1364 ms 32452 KB Output is correct
15 Correct 1516 ms 31564 KB Output is correct
16 Correct 1372 ms 32436 KB Output is correct
17 Correct 1357 ms 32600 KB Output is correct
18 Correct 1408 ms 32564 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 460 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 5 ms 440 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 5 ms 460 KB Output is correct
9 Correct 6 ms 456 KB Output is correct
10 Correct 1466 ms 32596 KB Output is correct
11 Correct 1130 ms 29572 KB Output is correct
12 Correct 1321 ms 30628 KB Output is correct
13 Correct 1397 ms 32484 KB Output is correct
14 Correct 1364 ms 32452 KB Output is correct
15 Correct 1516 ms 31564 KB Output is correct
16 Correct 1372 ms 32436 KB Output is correct
17 Correct 1357 ms 32600 KB Output is correct
18 Correct 1408 ms 32564 KB Output is correct
19 Runtime error 6 ms 588 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -