結果

問題 No.1341 真ん中を入れ替えて門松列
ユーザー 👑 NachiaNachia
提出日時 2021-01-15 23:11:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,629 bytes
コンパイル時間 2,516 ms
コンパイル使用メモリ 219,648 KB
実行使用メモリ 20,356 KB
最終ジャッジ日時 2024-11-26 17:19:56
合計ジャッジ時間 36,345 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
13,636 KB
testcase_01 AC 2 ms
13,196 KB
testcase_02 AC 2 ms
13,640 KB
testcase_03 AC 2 ms
13,036 KB
testcase_04 AC 2 ms
13,560 KB
testcase_05 AC 2 ms
13,428 KB
testcase_06 AC 51 ms
13,296 KB
testcase_07 TLE -
testcase_08 AC 9 ms
13,424 KB
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using ULL=unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

struct mcf{
static const int xN = 12002;

template<class T>
using nega_queue = priority_queue<T,vector<T>,greater<T>>;

struct Edge{ int u,v,r; LL c; LL d; };

int N;
int fSrc=12000;
int fSnk=12001;
vector<Edge> J;
vector<int> E[xN];

LL F;
LL fAns = 0;
LL fD[xN];
LL fPE[xN];
LL fP[xN]={};

void addEdge(int u,int v,LL c,LL d){
  E[u].push_back(J.size());
  J.push_back({u,v,(int)J.size()+1,c,d});
  E[v].push_back(J.size());
  J.push_back({v,u,(int)J.size()-1,0,-d});
}

void fDijkstra(){
  rep(i,N) fD[i]=fPE[i]=-1;
  nega_queue<pair<LL,pair<int,LL>>> Q; Q.push({0,{fSrc,-1}});
  while(Q.size()){
    LL d=Q.top().first;
    int p=Q.top().second.first;
    LL pre=Q.top().second.second;
    Q.pop();
    if(fD[p]!=-1) continue;
    fD[p]=d;
    fPE[p]=pre;
    for(int j:E[p]){
      if(J[j].c==0)continue;
      Q.push({d+J[j].d+fP[p]-fP[J[j].v],{J[j].v,j}});
    }
  }
  rep(i,N) fP[i]+=fD[i];
}

void flow(){
  fDijkstra();
  if(fD[fSnk]==-1){ F=0; fAns=-1; return; }
  LL c=1;
  int p=fSnk;
  while(p!=fSrc){
    J[fPE[p]].c-=c;
    J[J[fPE[p]].r].c+=c;
    fAns += (int)c * J[fPE[p]].d;
    p=J[fPE[p]].u;
  }
  F-=c;
}
} G;

int N;
ULL M;
ULL A[3000];
pair<ULL,ULL> ranges[3000];
pair<ULL,int> L[3000], R[3000];

int binsearchL(ULL x){
  int l=0,r=N+1;
  while(r-l>1){ int m=(l+r)/2; ((L[m].first<=x)?l:r)=m; }
  return l;
}
int binsearchR(ULL x){
  int l=0,r=N+1;
  while(r-l>1){ int m=(l+r)/2; ((L[m].first<=x)?l:r)=m; }
  return l;
}

const ULL xA=1000000000;

int main(){
  scanf("%d%llu",&N,&M);
  rep(i,N){ int a,b,c; scanf("%d%d%d",&a,&b,&c); if(a>c) swap(a,c); ranges[i]={a,c}; A[i]=b; }
  sort(A,A+N);
  rep(i,N) L[i]={ranges[i].first,i}; sort(L,L+N);
  rep(i,N) R[i]={ranges[i].second,i}; sort(R,R+N);
  G.N=N*4+2;
  G.fSrc=N*4; G.fSnk=N*4+1;
  rep(i,N) G.addEdge(G.fSrc,i,1,0);
  { int p=0; rep(i,N){ while(p<N){ if(A[i]>=L[p].first) p++; else{ G.addEdge(i,N+L[p].second,1,0); break; } } } }
  rep(i,N-1) G.addEdge(N+L[i].second,N+L[i+1].second,N,0);
  { int p=N-1; for(int i=N-1; i>=0; i--){ while(p>=0){ if(R[p].first>=A[i]) p--; else{ G.addEdge(i,N+N+R[p].second,1,xA-A[i]); break; } } } }
  rep(i,N-1) G.addEdge(N+N+R[i+1].second,N+N+R[i].second,N,0);
  rep(i,N){ G.addEdge(N+i,N+N+N+i,1,xA-ranges[i].second); G.addEdge(N+N+i,N+N+N+i,1,0); }
  rep(i,N) G.addEdge(N+N+N+i,G.fSnk,1,0);
  G.F=N;
  while(G.F) G.flow();
  if(G.fAns==-1){ printf("NO\n"); }
  else{
    printf("YES\n");
    if(xA*N-G.fAns>=M) printf("KADOMATSU!\n"); else printf("NO\n");
  }
  return 0;
}
0