結果

問題 No.168 ものさし
ユーザー BantakoBantako
提出日時 2018-06-20 19:19:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 134 ms / 2,000 ms
コード長 1,695 bytes
コンパイル時間 1,740 ms
コンパイル使用メモリ 177,380 KB
実行使用メモリ 21,176 KB
最終ジャッジ日時 2023-09-13 07:22:50
合計ジャッジ時間 3,596 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
7,460 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 5 ms
4,376 KB
testcase_11 AC 27 ms
7,420 KB
testcase_12 AC 94 ms
19,696 KB
testcase_13 AC 133 ms
19,960 KB
testcase_14 AC 134 ms
20,736 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 3 ms
4,376 KB
testcase_18 AC 8 ms
4,376 KB
testcase_19 AC 127 ms
19,892 KB
testcase_20 AC 134 ms
21,176 KB
testcase_21 AC 134 ms
20,596 KB
testcase_22 AC 133 ms
19,792 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:45:1: 警告: ISO C++ では型の無い ‘main’ の宣言を禁止しています [-Wreturn-type]
   45 | main(){
      | ^~~~
次のファイルから読み込み:  /usr/local/gcc7/include/c++/12.2.0/x86_64-pc-linux-gnu/bits/stdc++.h:41,
         次から読み込み:  main.cpp:1:
関数 ‘constexpr typename __gnu_cxx::__enable_if<std::__is_integer<_Tp>::__value, double>::__type std::sqrt(_Tp) [with _Tp = long long int]’ 内,
    inlined from ‘int main()’ at main.cpp:77:19:
/usr/local/gcc7/include/c++/12.2.0/cmath:476:28: 警告: ‘maxi’ may be used uninitialized [-Wmaybe-uninitialized]
  476 |     { return __builtin_sqrt(__x); }
      |              ~~~~~~~~~~~~~~^~~~~
main.cpp: 関数 ‘int main()’ 内:
main.cpp:65:8: 備考: ‘maxi’ はここで定義されています
   65 |     ll maxi;
      |        ^~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = int(a); i < int(b); ++i)
typedef long long ll;
typedef pair<int,int> P;
int INF = 1e9;
int MOD = 1e9+7;
const int MAX_N = 100000;
struct UnionFind{
    int par[MAX_N];
    void init(int n){
        for(int i = 0;i < n;i++)par[i] = i;
    }
    int root(int x){
        if(par[x] == x)return x;
        else return par[x] = root(par[x]);
    }
    bool same(int x,int y){
        return root(x) == root(y);
    }
    void unite(int x,int y){
        x = root(x);
        y = root(y);
        if(x == y)return;
        par[y] = x;
    }
};
ll sqrtll(ll x)
{
    ll a = 0, c = 0, y = 0, i = 0, t = x;
    while (t >>= 1)
    {
        ++i;
    }
    for (i += i & 1; i >= 0; i -= 2)
    {
        c = (y << 1 | 1) <= x >> i;
        a = a << 1 | c;
        y = y << 1 | c;
        x -= c * y << i;
        y += c;
    }
    return a;
}
main(){
    int N;
    cin >> N;
    vector< P > V(N);
    vector< pair<ll , P > > dist;
    rep(i,0,N){
        int a,b;
        cin >> a >> b;
        V[i] = P(a,b);
    }
    rep(i,0,N)rep(j,0,N){
        if(i == j)continue;
        ll dx = V[i].second - V[j].second;
        ll dy = V[i].first - V[j].first;

        dist.emplace_back(dx*dx + dy*dy, P(i,j));
    }
    sort(dist.begin(), dist.end());
    UnionFind uf;
    uf.init(N);
    ll maxi;
    for(auto p:dist){
        auto pi = p.second;
        uf.unite(pi.first, pi.second);

        if(uf.same(0,N-1)){
            maxi = p.first;
            break;
        }
    }
    //cout << maxi << endl;
    ll num;
    for(num = sqrt(maxi);num * num < maxi;num++){}
    num = (num + 9) / 10 * 10;
    cout << num << endl;

}
0