結果
問題 | No.1341 真ん中を入れ替えて門松列 |
ユーザー | chocorusk |
提出日時 | 2021-01-15 22:46:00 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 13,117 bytes |
コンパイル時間 | 3,606 ms |
コンパイル使用メモリ | 244,620 KB |
実行使用メモリ | 16,092 KB |
最終ジャッジ日時 | 2024-05-05 00:46:12 |
合計ジャッジ時間 | 15,174 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
10,624 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 20 ms
5,376 KB |
testcase_07 | AC | 319 ms
6,568 KB |
testcase_08 | AC | 7 ms
6,512 KB |
testcase_09 | AC | 340 ms
6,884 KB |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; //#define int ll #define rng(i,a,b) for(int i=int(a);i<int(b);i++) #define rep(i,b) rng(i,0,b) #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl #else #define dmp(x) void(0) #endif template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;} template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;} template<class t> using vc=vector<t>; template<class t> using vvc=vc<vc<t>>; using pi=pair<int,int>; using vi=vc<int>; template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p){ return os<<"{"<<p.a<<","<<p.b<<"}"; } template<class t> ostream& operator<<(ostream& os,const vc<t>& v){ os<<"{"; for(auto e:v)os<<e<<","; return os<<"}"; } #define mp make_pair #define mt make_tuple #define one(x) memset(x,-1,sizeof(x)) #define zero(x) memset(x,0,sizeof(x)) #ifdef LOCAL void dmpr(ostream&os){os<<endl;} template<class T,class... Args> void dmpr(ostream&os,const T&t,const Args&... args){ os<<t<<" "; dmpr(os,args...); } #define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__) #else #define dmp2(...) void(0) #endif using uint=unsigned; using ull=unsigned long long; template<class t,size_t n> ostream& operator<<(ostream&os,const array<t,n>&a){ return os<<vc<t>(all(a)); } template<int i,class T> void print_tuple(ostream&,const T&){ } template<int i,class T,class H,class ...Args> void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<<get<i>(t); print_tuple<i+1,T,Args...>(os,t); } template<class ...Args> ostream& operator<<(ostream&os,const tuple<Args...>&t){ os<<"{"; print_tuple<0,tuple<Args...>,Args...>(os,t); return os<<"}"; } template<class t> void print(t x,int suc=1){ cout<<x; if(suc==1) cout<<"\n"; if(suc==2) cout<<" "; } ll read(){ ll i; cin>>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } pi readpi(int off=0){ int a,b;cin>>a>>b; return pi(a+off,b+off); } template<class T> void print(const vector<T>&v,int suc=1){ rep(i,v.size()) print(v[i],i==int(v.size())-1?suc:2); } string readString(){ string s; cin>>s; return s; } template<class T> T sq(const T& t){ return t*t; } //#define CAPITAL void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<"\n"; #else cout<<"Yes"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } ll mask(int i){ return (ll(1)<<i)-1; } bool inc(int a,int b,int c){ return a<=b&&b<=c; } template<class t> void mkuni(vc<t>&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] #ifdef LOCAL static mt19937_64 gen; #else static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count()); #endif return uniform_int_distribution<ll>(l, r)(gen); } template<class t> void myshuffle(vc<t>&a){ rep(i,si(a))swap(a[i],a[rand_int(0,i)]); } template<class t> int lwb(const vc<t>&v,const t&a){ return lower_bound(all(v),a)-v.bg; } vvc<int> readGraph(int n,int m){ vvc<int> g(n); rep(i,m){ int a,b; cin>>a>>b; //sc.read(a,b); a--;b--; g[a].pb(b); g[b].pb(a); } return g; } vvc<int> readTree(int n){ return readGraph(n,n-1); } using int128=__int128_t; using uint128=unsigned __int128_t; //-が来た場合はまだわからん istream& operator>>(istream&is,int128&res){ res=0; string s;is>>s; int head=0; int128 w=1; if(s[0]=='_'){ w=-1; head++; } while(head<si(s)){ res=res*10+s[head++]-'0'; } res*=w; return is; } ostream& operator<<(ostream&os,int128 i){ if(i==0) return os<<0; static char buf[100]; if(i<0){ os<<"-"; i=-i; } int p=0; while(i){ buf[p++]='0'+i%10; i/=10; } reverse(buf,buf+p); buf[p]=0; return os<<buf; } int128 abs128(int128 a){ return a<0?-a:a; } int botbit(int128 a){ const int128 m=(int128(1)<<64)-1; if(a&m)return __builtin_ctzll(ll(a)); else return __builtin_ctzll(ll(a>>64)); } int128 gcd(int128 a,int128 b){ if(a<0)a=-a; if(b<0)b=-b; if(a==0)return b; if(b==0)return a; int128 s=botbit(a|b); a>>=botbit(a); do{ b>>=botbit(b); if(a>b)swap(a,b); b-=a; }while(b); return a<<s; } const int128 inf128=int128(1)<<122; //work without define int ll //maxflow with small constant //CF Global11 G //bfs を途中で打ち切る,dfs が逆順 //ae の 4th argument は逆辺の capacity //無向辺を貼りたい場合などに,有効・・・ template<class d> struct maxflow{ struct E{ int to,nx; d cap; }; vc<E> es; vi head,q; vc<pi> itr,lv; int curt; maxflow(int n):head(n,-1),q(n),itr(n),lv(n),curt(0){} int ae(int s,int t,d c,d c2=0){ int pres=head[s]; int pret=head[t]; head[s]=si(es); es.pb({t,pres,c}); head[t]=si(es); es.pb({s,pret,c2}); return head[s]; } void bfs(int s,int t=-1){ lv[s]=pi(0,curt); int l=0,r=0; q[r++]=s; while(l<r){ int v=q[l++]; for(int id=head[v];id!=-1;id=es[id].nx){ auto e=es[id]; if(e.cap>0&&lv[e.to].b<curt){ lv[e.to]=pi(lv[v].a+1,curt); q[r++]=e.to; if(e.to==t)return; } } } } d dfs(int v,int t,d f){ if(v==t)return f; if(itr[v].b<curt)itr[v]=pi(head[v],curt); d res=0; while(itr[v].a!=-1){ E& e=es[itr[v].a]; E& rev=es[itr[v].a^1]; if(rev.cap>0&&lv[e.to].a==lv[v].a-1&&lv[e.to].b==curt){ d a=dfs(e.to,t,min(f,rev.cap)); if(a>0){ rev.cap-=a; e.cap+=a; res+=a; f-=a; if(f<=0)break; } } itr[v].a=e.nx; } return res; } d calc(int s,int t,d mx=inf){ d f=0; while(f<mx){ curt++; bfs(s,t); if(lv[t].b<curt) return f; f+=dfs(t,s,mx-f); } return f; } }; //以下のパラメータを問題に応じていじって最強の定数倍を手に入れよう! //- eps を割る scale //- refine の必要性を確かめる嘘 bellman-ford のループ回数 //- dfs を途中で打ち切る深さ //VERIFY: //yosupo mincost b flow //AGC034D //work without define int ll //captype=O(cap*max(n,m)) //costtype=O(cost*n*max(n,m)) //あらゆる関数が破壊的 template<class captype,class costtype,class anstype> struct costscaling{ struct E{ int to,rev; captype cap; costtype cost; }; int n; costtype eps; vvc<E> g; vc<pi> idx; vi itr,q; vc<bool> inq,vis; vc<captype> fl,off; vc<costtype> p; maxflow<captype> mf; anstype ans; costscaling(int nn):n(nn),g(n),itr(n),inq(n),vis(n),fl(n),p(n),mf(n+2),ans(0){} void ae(int s,int t,captype l,captype r,costtype c){ assert(l<=r); if(s==t){ idx.eb(-1,-1); captype f=c>0?l:r; ans+=anstype(c)*f; off.pb(f); }else{ c*=(n+1); idx.eb(s,si(g[s])); off.pb(r); fl[s]-=l; fl[t]+=l; g[s].pb({t,si(g[t]),r-l,c}); g[t].pb({s,si(g[s])-1,0,-c}); } mf.ae(s,t,r-l); } void add_excess(int v,captype c){ fl[v]+=c; } void add_demand(int v,captype c){ fl[v]-=c; } costtype getcost(int v,const E&e){ return e.cost-p[e.to]+p[v]; } void addq(int v){ if(fl[v]>0&&!inq[v]){ q.pb(v); inq[v]=true; } } void push(int v,E&e,captype a){ int to=e.to,j=e.rev; assert(0<=a); assert(a<=e.cap); e.cap-=a; g[to][j].cap+=a; fl[v]-=a; fl[to]+=a; addq(to); } void relabel(int v){ p[v]=numeric_limits<costtype>::min()/2; for(const auto&e:g[v]){ if(e.cap>0){ chmax(p[v],-eps-e.cost+p[e.to]); } } itr[v]=0; } bool dfs(int v,int dep,captype come){ if(vis[v])return false; vis[v]=true; if(fl[v]<0||dep==4){ vis[v]=false; return true; }else{ while(itr[v]<si(g[v])){ auto&e=g[v][itr[v]]; if(e.cap&&getcost(v,e)<0){ auto u=min(e.cap,fl[v]+come); if(dfs(e.to,dep+1,u)){ push(v,e,u); vis[v]=false; return true; } } itr[v]++; } relabel(v); vis[v]=false; return false; } } bool slv(){ int m=si(idx); { if(accumulate(all(fl),captype(0))){ //demand and excess don't match return false; } captype f=0; rep(i,n)if(fl[i]>0){ f+=fl[i]; mf.ae(n,i,fl[i]); }else if(fl[i]<0){ mf.ae(i,n+1,-fl[i]); } captype did=mf.calc(n,n+1,f); if(did<f)return false; rep(k,m)if(idx[k].a!=-1){ auto&e=g[idx[k].a][idx[k].b]; e.cap=mf.es[k*2].cap; g[e.to][e.rev].cap=mf.es[k*2+1].cap; } rep(i,n)fl[i]=0; } while(1){ //now eps-optimal rep(i,n)assert(fl[i]==0); eps=0; rep(v,n)for(const auto&e:g[v])if(e.cap>0)chmax(eps,-getcost(v,e)); if(eps<=1)break; eps=max(eps/8,costtype(1)); bool need=true; rep(_,5){ bool upd=false; rep(v,n)for(const auto&e:g[v])if(e.cap>0){ if(chmin(p[e.to],p[v]+e.cost+eps)) upd=true; } if(!upd){ need=false; break; } } if(!need)continue; rep(v,n)for(auto&e:g[v])if(getcost(v,e)<0) push(v,e,e.cap); q.clear(); rep(i,n){ itr[i]=0; inq[i]=false; } int qb=0; rep(i,n)addq(i); while(qb<si(q)){ int v=q[qb++]; inq[v]=false; while(fl[v]>0)dfs(v,0,0); /*while(fl[v]>0){ if(itr[v]==si(g[v])) relabel(v); while(itr[v]<si(g[v])){ auto&e=g[v][itr[v]]; if(e.cap&&getcost(v,e)<0){ push(v,e,min(e.cap,fl[v])); if(fl[v]==0)break; } itr[v]++; } }*/ } } rep(i,n)assert(fl[i]==0); rep(v,n)for(const auto&e:g[v])if(e.cap>0)assert(getcost(v,e)>=-1); rep(v,n)for(auto&e:g[v])e.cost/=(n+1); return true; } pair<anstype,vc<captype>> get_solution(){ rep(i,si(off))if(idx[i].a!=-1){ const auto&e=g[idx[i].a][idx[i].b]; off[i]-=e.cap; ans+=anstype(e.cost)*off[i]; } return mp(ans,off); } vc<costtype> get_potential(){ rep(i,n)p[i]/=(n+1); rep(_,n+1){ bool upd=false; rep(v,n)for(const auto&e:g[v])if(e.cap>0){ if(chmin(p[e.to],p[v]+e.cost)) upd=true; } if(!upd)break; assert(_<n); } return p; } }; void test(){ int n=100,m=100000; costscaling<ll,ll,int128> cs(n); rep(i,n)cs.add_excess(i,0); rep(i,m){ int s,t,l,u,c;//cin>>s>>t>>l>>u>>c; s=rand_int(0,n-1); t=rand_int(0,n-1); l=rand_int(-ten(9),ten(9)); u=rand_int(-ten(9),ten(9)); if(u<l)swap(l,u); c=rand_int(-ten(9),ten(9)); cs.ae(s,t,l,u,c); } if(cs.slv()){ int128 ans; vc<ll> f; tie(ans,f)=cs.get_solution(); vc<ll> p=cs.get_potential(); cout<<ans<<endl; print(p); print(f); }else{ cout<<"infeasible"<<endl; } } void slv(){ int n; ll m; cin>>n>>m; ll a[3030], b[3030], c[3030]; using P=pair<ll, ll>; vector<P> v(n); for(int i=0; i<n; i++){ cin>>a[i]>>b[i]>>c[i]; if(a[i]>c[i]) swap(a[i], c[i]); v[i]=P(a[i], c[i]); } sort(v.begin(), v.end()); vector<P> w(n); for(int i=0; i<n; i++){ w[i]=P(v[i].second, i); } sort(w.begin(), w.end()); const ll MAX=1e9; costscaling<ll,ll,int128> cs(4*n); for(int i=0; i<n; i++){ cs.add_excess(i, 1); } for(int i=0; i<n; i++){ int p=lower_bound(v.begin(), v.end(), P(b[i], MAX+7))-v.begin(); if(p<n){ cs.ae(i, n+p, 0, 1, 0); } } for(int i=0; i<n-1; i++) cs.ae(n+i, n+i+1, 0, n, 0); for(int i=0; i<n; i++){ int p=lower_bound(w.begin(), w.end(), P(b[i], 0))-w.begin(); if(p>0){ cs.ae(i, 2*n+p-1, 0, 1, MAX-b[i]); } } for(int i=0; i<n-1; i++) cs.ae(2*n+i+1, 2*n+i, 0, n, 0); for(int i=0; i<n; i++){ cs.ae(n+i, 3*n+i, 0, 1, MAX-v[i].second); int p=w[i].second; cs.ae(2*n+i, 3*n+p, 0, 1, 0); } for(int i=0; i<n; i++) cs.add_demand(3*n+i, 1); if(!cs.slv()){ cout<<"NO"<<endl; return; } ll f=cs.get_solution().first; cout<<"YES"<<endl; //cout<<MAX*n-res.second<<endl; if(MAX*n-f>=m) cout<<"KADOMATSU!"<<endl; else cout<<"NO"<<endl; } signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); //int t;cin>>t;rep(_,t) //test(); slv(); }