結果

問題 No.168 ものさし
コンテスト
ユーザー hogeover30
提出日時 2015-03-24 02:46:09
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,116 bytes
コンパイル時間 596 ms
コンパイル使用メモリ 53,300 KB
最終ジャッジ日時 2024-11-14 19:00:58
合計ジャッジ時間 1,146 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:8:5: error: ‘vector’ does not name a type
    8 |     vector<int> id;
      |     ^~~~~~
main.cpp: In constructor ‘unionfind::unionfind(int)’:
main.cpp:11:9: error: ‘id’ was not declared in this scope; did you mean ‘void’?
   11 |         id=vector<int>(size);
      |         ^~
      |         void
main.cpp:11:12: error: ‘vector’ was not declared in this scope
   11 |         id=vector<int>(size);
      |            ^~~~~~
main.cpp:3:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    2 | #include <algorithm>
  +++ |+#include <vector>
    3 | using namespace std;
main.cpp:11:19: error: expected primary-expression before ‘int’
   11 |         id=vector<int>(size);
      |                   ^~~
main.cpp: In member function ‘int unionfind::root(int)’:
main.cpp:14:30: error: ‘id’ was not declared in this scope; did you mean ‘void’?
   14 |     int root(int x) { return id[x]=id[x]==x?x:root(id[x]); }
      |                              ^~
      |                              void
main.cpp: In member function ‘void unionfind::unite(int, int)’:
main.cpp:15:64: error: ‘id’ was not declared in this scope; did you mean ‘void’?
   15 |     void unite(int x, int y) { x=root(x); y=root(y); if (x!=y) id[x]=y; }
      |                                                                ^~
      |                                                                void
main.cpp: At global scope:
main.cpp:19:1: error: ‘vector’ does not name a type
   19 | vector<pair<ll, ll>> p;
      | ^~~~~~
main.cpp: In function ‘ll dist(int, int)’:
main.cpp:25:16: error: ‘p’ was not declared in this scope
   25 |     return sqr(p[i].first-p[j].first)+sqr(p[i].second-p[j].second);
      |                ^
main.cpp:24:18: note: in definition of macro ‘sqr’
   24 | #define sqr(x) ((x)*(x))
      |                  ^
main.cpp: In function ‘int main()’:
main.cpp:30:9: error

ソースコード

diff # 

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

struct unionfind {
    vector<int> id;
    int size;
    unionfind(int size_):size(size_) {
        id=vector<int>(size);
        for(int i=0;i<size;++i) id[i]=i;
    }
    int root(int x) { return id[x]=id[x]==x?x:root(id[x]); }
    void unite(int x, int y) { x=root(x); y=root(y); if (x!=y) id[x]=y; }
    bool same(int x, int y) { return root(x)==root(y); }
};

vector<pair<ll, ll>> p;
int n;

ll dist(int i, int j)
{
#define sqr(x) ((x)*(x))
    return sqr(p[i].first-p[j].first)+sqr(p[i].second-p[j].second);
}
int main()
{
    while (cin>>n) {
        p=vector<pair<ll,ll>>(n);
        for(auto& v: p) { ll x, y; cin>>x>>y; v=make_pair(x, y); }
        ll L=0, R=sqrt(dist(0, n-1))*2;
        while (R-L>2) {
            ll M=(L+R)/2;
            unionfind a(n);
            for(int i=0;i<n;++i) for(int j=0;j<n;++j) if (i!=j and dist(i, j)<=M*M)
                a.unite(i, j);
            if (a.same(0, n-1))
                R=M+1;
            else
                L=M;
        }
        cout<<(R-1+9)/10*10<<endl;
    }
}
0