結果

問題 No.1607 Kth Maximum Card
ユーザー 👑 tute7627tute7627
提出日時 2021-04-28 02:42:34
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,816 bytes
コンパイル時間 2,121 ms
コンパイル使用メモリ 209,904 KB
実行使用メモリ 33,592 KB
最終ジャッジ日時 2023-09-20 12:32:25
合計ジャッジ時間 48,449 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 3 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 3 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 513 ms
15,592 KB
testcase_09 AC 309 ms
13,476 KB
testcase_10 AC 270 ms
15,556 KB
testcase_11 AC 53 ms
6,700 KB
testcase_12 AC 270 ms
13,060 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 440 ms
33,592 KB
testcase_23 AC 448 ms
33,560 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 AC 1,188 ms
9,320 KB
testcase_34 WA -
testcase_35 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

template<typename T>
struct BIT{
  int n;
  int k=1;
  vector<T>data;
  BIT() = default;
  BIT(int size):n(size){
    data.assign(n,0);
    while(k*2<=n)k*=2;
  }
  void add(int a,T w){
    for(int i=a+1;i<=n;i+=i&-i)data[i-1]+=w;
  }
  T sum(int a){//[0,a)
	  if(a<=0)return 0;
    T ret = 0;
    for(int i=a;i>0;i-=i&-i)ret+=data[i-1];
    return ret;
  }
  //[a,b)
  T sum(int a,int b){return a>=b?0:sum(b)-sum(a);}
  T operator[](int pos){
    return sum(pos,pos+1);
  }
  int lower_bound(int x){
    int ret=0;    
    for(int i=k;i>0;i/=2){
      if(ret+i<=n&&data[ret+i-1]<x){
        x-=data[ret+i-1];
        ret+=i;
      }
    }
    return ret;
  }
  void print(){
    for(int i=0;i<n;i++){
      if(i!=0)cout<<" ";
      cout<<(*this)[i];
    }
    cout<<endl;
  }
};

struct edge{
  int to;
  int c;
};

int main(){
  int n, m, k;
  cin >> n >> m >> k;
  
  vector<vector<edge>>g(n);
  for(int i = 0; i < m; i++){
    int u, v, c;
    cin >> u >> v >> c;
    u--, v--;
    g[u].push_back({v, c});
    g[v].push_back({u, c});
  }
  for(int i = 0; i < n; i++){
    sort(g[i].begin(), g[i].end(), [](edge x,edge y){
      return x.c < y.c;
    });
  }
  const int mx = 200000;
  BIT<int>bit(200005);
  bit.add(mx,k);
  int ret = mx;
  long long start = clock();
  auto calc = [&](){
    return mx - bit.lower_bound(k);
  };
  vector<bool>used(n);
  auto dfs = [&](auto &&f, int v)->void{
    if(clock() - start >= 1.9 * CLOCKS_PER_SEC)return;
    if(v == n - 1){
      ret = min(ret, calc());
      return;
    }
    if(calc() >= ret)return;
    used[v] = true;
    for(auto e:g[v]){
      if(used[e.to])continue;
      bit.add(mx - e.c, 1);
      f(f, e.to);
      bit.add(mx - e.c, -1);
    }
    used[v] = false;
  };
  dfs(dfs, 0);
  cout << ret << endl;
}
0