oj.uz

Submission #522520

# Submission time Handle Problem Language Result Execution time Memory
522520 2022-02-05T05:57:49 Z PCTprobability Swapping Cities (APIO20_swap) C++14
37 / 100
 2000 ms 11196 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -