結果

問題 No.1607 Kth Maximum Card
ユーザー tute7627
提出日時 2021-04-28 02:42:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,816 bytes
コンパイル時間 2,475 ms
コンパイル使用メモリ 205,712 KB
最終ジャッジ日時 2025-01-21 01:34:33
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 20
権限があれば一括ダウンロードができます

ソースコード

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