답안 #522520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522520	2022-02-05T05:57:49 Z	PCTprobability	자매 도시 (APIO20_swap)	C++14	37 / 100	2000 ms	11196 KB

swap

#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
using ll = int;
using ld = long double;
using ull = unsigned long long;
#define endl "\n"
typedef pair<int,int> Pii;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(x) begin(x), end(x)
#define PB push_back
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(s) (s).begin(),(s).end()
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
#define rever(vec) reverse(vec.begin(), vec.end())
#define sor(vec) sort(vec.begin(), vec.end())
#define fi first
#define se second
#define pb push_back
#define P pair<ll,ll>
#define PQminll priority_queue<ll, vector<ll>, greater<ll>>
#define PQmaxll priority_queue<ll,vector<ll>,less<ll>>
#define PQminP priority_queue<P, vector<P>, greater<P>>
#define PQmaxP priority_queue<P,vector<P>,less<P>>
#define NP next_permutation
//typedef string::const_iterator State;
//class ParseError {};
//const ll mod = 1000000009;
const ll mod = 998244353;
//const ll mod = 1000000007;
const ll inf = 4100000000000000000ll;
const ld eps = ld(0.000000001);
const long double pi = 3.141592653589793;
template<class T>void vcin(vector<T> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}
template<class T,class K>void vcin(vector<T> &n,vector<K> &m){for(int i=0;i<int(n.size());i++) cin>>n[i]>>m[i];}
template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}
template<class T>void vcin(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cin>>n[i][j];}}}
template<class T>void vcout(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cout<<n[i][j]<<" ";}cout<<endl;}cout<<endl;}
void yes(bool a){cout<<(a?"yes":"no")<<endl;}
void YES(bool a){cout<<(a?"YES":"NO")<<endl;}
void Yes(bool a){cout<<(a?"Yes":"No")<<endl;}
void possible(bool a){ cout<<(a?"possible":"impossible")<<endl; }
void Possible(bool a){ cout<<(a?"Possible":"Impossible")<<endl; }
void POSSIBLE(bool a){ cout<<(a?"POSSIBLE":"IMPOSSIBLE")<<endl; }
template<class T>void print(T a){cout<<a<<endl;}
template<class T,class F>void print(pair<T,F> a){cout<<a.fi<<" "<<a.se<<endl;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0;}
template<class T> void ifmin(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}
template<class T> void ifmax(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}
ll fastgcd(ll u,ll v){ll shl=0;while(u&&v&&u!=v){bool eu=!(u&1);bool ev=!(v&1);if(eu&&ev){++shl;u>>=1;v>>=1;}else if(eu&&!ev){u>>=1;}else if(!eu&&ev){v>>=1;}else if(u>=v){u=(u-v)>>1;}else{ll tmp=u;u=(v-u)>>1;v=tmp;}}return !u?v<<shl:u<<shl;}
ll modPow(ll a, ll n, ll mod) { if(mod==1) return 0;ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }
vector<ll> divisor(ll x){ vector<ll> ans; for(ll i = 1; i * i <= x; i++){ if(x % i == 0) {ans.push_back(i); if(i*i!=x){ ans.push_back(x / ans[i]);}}}sor(ans); return ans; }
ll pop(ll x){return __builtin_popcountll(x);}
ll poplong(ll x){ll y=0;while(x){x/=2;y++;}return y;}
 
void cincout() {
  ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
  cout<< fixed << setprecision(10);
}
class UnionFind{
public:
  vector<ll> par;
  vector<ll> siz;
  UnionFind(ll sz_):par(sz_),siz(sz_,1ll){
    for(int i=0;i<sz_;i++) par[i]=i;
  }
  void init(ll sz_){
    par.resize(sz_);
    siz.assign(sz_,1ll);
    for(int i=0;i<sz_;i++) par[i]=i;
  }
  ll root(ll x){
    while(par[x]!=x){
      x=par[x]=par[par[x]];
    }
    return x;
  }
  bool merge(ll x,ll y){
    x=root(x);
    y=root(y);
    if(x==y) return false;
    if(siz[x]<siz[y]) swap(x,y);
    siz[x]+=siz[y];
    par[y]=x;
    return true;
  }
  bool issame(ll x,ll y){
    return root(x)==root(y);
  }
  ll size(ll x){
    return siz[root(x)];
  }
};
vector<ll> u,v,w;
ll n,m;
int getMinimumFuelCapacity(int X,int Y){
  int x=X,y=Y;
  ll ok=0,ng=1000000100;
  while(abs(ok-ng)>1){
    ll t=(ok+ng)/2;
    UnionFind uf(n);
    vector<ll> d(n);
    for(int j=0;j<m;j++){
      if(w[j]<=t){
        uf.merge(u[j],v[j]);
        d[u[j]]++;
        d[v[j]]++;
      }
    }
    if(!uf.issame(x,y)){
      ok=t;
      continue;
    }
    vector<ll> f;
    for(int i=0;i<n;i++){
      if(uf.issame(x,i)) f.pb(d[i]);
    }
    sor(f);
    if(f[int(f.size())-1]<=2&&f[1]==1){
      ok=t;
    }
    else{
      ng=t;
    }
  }
  if(ng==1000000100) ng=-1;
  return ng;
}
void init(int N,int M,vector<int> U,vector<int> V,vector<int> W){
  n=N;
  m=M;
  u=U;
  v=V;
  w=W;
}

Compilation message

swap.cpp:39:16: warning: overflow in conversion from 'long long int' to 'll' {aka 'int'} changes value from '4100000000000000000' to '-82182144' [-Woverflow]
   39 | const ll inf = 4100000000000000000ll;
      |                ^~~~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	292 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	4 ms	292 KB	Output is correct
5	Correct	4 ms	356 KB	Output is correct
6	Correct	5 ms	332 KB	Output is correct
7	Correct	5 ms	332 KB	Output is correct
8	Correct	4 ms	332 KB	Output is correct
9	Correct	208 ms	5568 KB	Output is correct
10	Correct	513 ms	6596 KB	Output is correct
11	Correct	677 ms	6524 KB	Output is correct
12	Correct	698 ms	6868 KB	Output is correct
13	Correct	776 ms	7008 KB	Output is correct
14	Execution timed out	2055 ms	6268 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	292 KB	Output is correct
3	Execution timed out	2098 ms	10780 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	292 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	4 ms	292 KB	Output is correct
5	Correct	4 ms	356 KB	Output is correct
6	Correct	5 ms	332 KB	Output is correct
7	Correct	5 ms	332 KB	Output is correct
8	Correct	4 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	3 ms	324 KB	Output is correct
11	Correct	4 ms	300 KB	Output is correct
12	Correct	4 ms	332 KB	Output is correct
13	Correct	4 ms	332 KB	Output is correct
14	Correct	3 ms	332 KB	Output is correct
15	Correct	4 ms	332 KB	Output is correct
16	Correct	4 ms	332 KB	Output is correct
17	Correct	4 ms	332 KB	Output is correct
18	Correct	4 ms	332 KB	Output is correct
19	Correct	3 ms	332 KB	Output is correct
20	Correct	4 ms	332 KB	Output is correct
21	Correct	5 ms	348 KB	Output is correct
22	Correct	3 ms	292 KB	Output is correct
23	Correct	3 ms	332 KB	Output is correct
24	Correct	5 ms	332 KB	Output is correct
25	Correct	7 ms	332 KB	Output is correct
26	Correct	6 ms	296 KB	Output is correct
27	Correct	4 ms	332 KB	Output is correct
28	Correct	5 ms	332 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	292 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	4 ms	292 KB	Output is correct
6	Correct	4 ms	356 KB	Output is correct
7	Correct	5 ms	332 KB	Output is correct
8	Correct	5 ms	332 KB	Output is correct
9	Correct	4 ms	332 KB	Output is correct
10	Correct	208 ms	5568 KB	Output is correct
11	Correct	513 ms	6596 KB	Output is correct
12	Correct	677 ms	6524 KB	Output is correct
13	Correct	698 ms	6868 KB	Output is correct
14	Correct	776 ms	7008 KB	Output is correct
15	Correct	3 ms	324 KB	Output is correct
16	Correct	4 ms	300 KB	Output is correct
17	Correct	4 ms	332 KB	Output is correct
18	Correct	4 ms	332 KB	Output is correct
19	Correct	3 ms	332 KB	Output is correct
20	Correct	4 ms	332 KB	Output is correct
21	Correct	4 ms	332 KB	Output is correct
22	Correct	4 ms	332 KB	Output is correct
23	Correct	4 ms	332 KB	Output is correct
24	Correct	3 ms	332 KB	Output is correct
25	Correct	4 ms	332 KB	Output is correct
26	Correct	5 ms	348 KB	Output is correct
27	Correct	3 ms	292 KB	Output is correct
28	Correct	3 ms	332 KB	Output is correct
29	Correct	5 ms	332 KB	Output is correct
30	Correct	7 ms	332 KB	Output is correct
31	Correct	6 ms	296 KB	Output is correct
32	Correct	4 ms	332 KB	Output is correct
33	Correct	5 ms	332 KB	Output is correct
34	Correct	24 ms	1148 KB	Output is correct
35	Correct	788 ms	6684 KB	Output is correct
36	Correct	789 ms	6912 KB	Output is correct
37	Correct	838 ms	6564 KB	Output is correct
38	Correct	847 ms	6540 KB	Output is correct
39	Correct	749 ms	6484 KB	Output is correct
40	Correct	786 ms	5956 KB	Output is correct
41	Correct	728 ms	6840 KB	Output is correct
42	Correct	845 ms	6560 KB	Output is correct
43	Correct	676 ms	6552 KB	Output is correct
44	Correct	639 ms	6832 KB	Output is correct
45	Correct	594 ms	8592 KB	Output is correct
46	Correct	866 ms	6548 KB	Output is correct
47	Correct	852 ms	6640 KB	Output is correct
48	Correct	734 ms	7068 KB	Output is correct
49	Correct	78 ms	8548 KB	Output is correct
50	Correct	107 ms	6808 KB	Output is correct
51	Correct	409 ms	7420 KB	Output is correct
52	Correct	847 ms	9568 KB	Output is correct
53	Correct	619 ms	10320 KB	Output is correct
54	Correct	975 ms	11196 KB	Output is correct
55	Correct	773 ms	6672 KB	Output is correct
56	Correct	834 ms	10136 KB	Output is correct

Subtask #5

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	292 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	4 ms	292 KB	Output is correct
5	Correct	4 ms	356 KB	Output is correct
6	Correct	5 ms	332 KB	Output is correct
7	Correct	5 ms	332 KB	Output is correct
8	Correct	4 ms	332 KB	Output is correct
9	Correct	208 ms	5568 KB	Output is correct
10	Correct	513 ms	6596 KB	Output is correct
11	Correct	677 ms	6524 KB	Output is correct
12	Correct	698 ms	6868 KB	Output is correct
13	Correct	776 ms	7008 KB	Output is correct
14	Execution timed out	2055 ms	6268 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #6

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	292 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	4 ms	292 KB	Output is correct
6	Correct	4 ms	356 KB	Output is correct
7	Correct	5 ms	332 KB	Output is correct
8	Correct	5 ms	332 KB	Output is correct
9	Correct	4 ms	332 KB	Output is correct
10	Correct	208 ms	5568 KB	Output is correct
11	Correct	513 ms	6596 KB	Output is correct
12	Correct	677 ms	6524 KB	Output is correct
13	Correct	698 ms	6868 KB	Output is correct
14	Correct	776 ms	7008 KB	Output is correct
15	Execution timed out	2055 ms	6268 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-