結果

問題 No.1341 真ん中を入れ替えて門松列
コンテスト
ユーザー 👑 Nachia
提出日時 2021-01-15 23:11:50
言語 C++17(gcc12)
(gcc 12.4.0 + boost 1.90.0)
コンパイル:
g++-12 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,629 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,628 ms
コンパイル使用メモリ 219,584 KB
実行使用メモリ 12,924 KB
最終ジャッジ日時 2026-06-16 19:20:12
合計ジャッジ時間 5,530 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 2 TLE * 1 -- * 11
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:88:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   88 |   scanf("%d%llu",&N,&M);
      |   ~~~~~^~~~~~~~~~~~~~~~
main.cpp:89:29: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   89 |   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; }
      |                        ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#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