| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 429714 |
2021-06-16T08:54:34 Z |
장태환(#7566) |
Power plants (CPSPC17_power) |
C++17 |
|
5 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;
}
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;
dfs(0,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);
}
}
}
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:91: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]
91 | for(i=0;i<f.size();i++)
| ~^~~~~~~~~
Main.cpp:97: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]
97 | for(i=0;i<sr.size();i++)
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
