結果

問題 No.168 ものさし
ユーザー Bantako
提出日時 2018-06-20 19:18:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,696 bytes
コンパイル時間 1,753 ms
コンパイル使用メモリ 178,196 KB
実行使用メモリ 19,932 KB
最終ジャッジ日時 2024-06-30 17:26:39
合計ジャッジ時間 3,403 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18 WA * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main(){
      | ^~~~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:41,
                 from main.cpp:1:
In function '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:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/cmath:476:28: warning: 'maxi' may be used uninitialized [-Wmaybe-uninitialized]
  476 |     { return __builtin_sqrt(__x); }
      |              ~~~~~~~~~~~~~~^~~~~
main.cpp: In function 'int main()':
main.cpp:65:8: note: 'maxi' was declared here
   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