oj.uz

Submission #429702

# Submission time Handle Problem Language Result Execution time Memory
429702 2021-06-16T08:50:02 Z 장태환(#7566) Power plants (CPSPC17_power) C++17
0 / 100
 6 ms 456 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;
    }
    int s=0,e=1LL<<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;
        dfs(0,1);
        if(ans)
            s=m;
        else
            e=m-1;
    }
    cout <<s<<'\n';
    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);
                }
            }
        }
    dfs(0,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:84: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]
   84 |     for(i=0;i<f.size();i++)
      |             ~^~~~~~~~~
Main.cpp:90: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]
   90 |     for(i=0;i<sr.size();i++)
      |             ~^~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 65.0

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