結果

問題 No.3372 Suitable Constraint
コンテスト
ユーザー butsurizuki
提出日時 2025-11-21 21:30:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 138 ms / 2,000 ms
コード長 1,877 bytes
コンパイル時間 3,309 ms
コンパイル使用メモリ 299,376 KB
実行使用メモリ 35,672 KB
最終ジャッジ日時 2025-11-21 21:30:57
合計ジャッジ時間 5,682 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using pl=pair<ll,ll>;

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    ll n;
    cin >> n;
    vector<pl> a(n);
    vector<pl> pos,neg,zero;
    for(ll i=0;i<n;i++){
      cin >> a[i].first;
      a[i].second=i;
      if(a[i].first>0){pos.push_back(a[i]);}
      else if(a[i].first<0){neg.push_back(a[i]);}
      else{zero.push_back(a[i]);}
    }
    sort(pos.begin(),pos.end());
    sort(neg.begin(),neg.end());
    vector<pair<ll,pl>> eg;
    for(ll i=0;i<n;i++){
      if(pos.size()>0){
        eg.push_back({pos[0].first*a[i].first,{pos[0].second,a[i].second}});
        eg.push_back({pos.back().first*a[i].first,{pos.back().second,a[i].second}});
      }
      if(neg.size()>0){
        eg.push_back({neg[0].first*a[i].first,{neg[0].second,a[i].second}});
        eg.push_back({neg.back().first*a[i].first,{neg.back().second,a[i].second}});
      }
      if(zero.size()>0){
        eg.push_back({zero[0].first*a[i].first,{zero[0].second,a[i].second}});
      }
    }
    sort(eg.rbegin(),eg.rend());
    UnionFind uf(n);
    for(auto &nx : eg){
      // cout << nx.second.first << " " << nx.second.second << "\n";
      uf.unionSet(nx.second.first,nx.second.second);
      if(uf.size(0)==n){
        cout << nx.first << "\n";
        break;
      }
    }
  }
  return 0;
}
0