Submission #147912

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
147912	2019-08-31 06:51:06	starwh03	문명 (KOI17_civilization)	C++14	19 / 100	4 ms	504 KiB

civilization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
int miku[2100];
int in[2100][2];
struct s
{
    int d,a,b;
    bool operator<(s a){return a.d>d;}
};
vector<s> cone;
int uni(int i){return miku[i]<0?i:miku[i]=uni(miku[i]);}
int dis(int a,int b){return abs(in[a][0]-in[b][0])+abs(in[a][1]-in[b][1]);}
int main()
{
    int n,m,mini=0;
    cin>>n>>m;
    for(int i=0;i<m;i++)cin>>in[i][0]>>in[i][1],miku[i]=-i-1;
    for(int i=0;i<m;i++)for(int j=i+1;j<m;j++)cone.push_back({dis(i,j),i,j});
    sort(cone.begin(),cone.end());
    for(int i=0;i<cone.size();i++)
        if(uni(cone[i].a)!=uni(cone[i].b))mini=cone[i].d,miku[uni(cone[i].a)]=uni(cone[i].b);
    cout<<mini/2;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

civilization.cpp: In function 'int main()':
civilization.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<cone.size();i++)
                 ~^~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 0 / 35
• Subtask 3: 0 / 46