結果
問題 | No.2160 みたりのDominator |
ユーザー | maroon_kuri |
提出日時 | 2022-12-29 23:16:11 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 250 ms / 2,000 ms |
コード長 | 8,112 bytes |
コンパイル時間 | 4,073 ms |
コンパイル使用メモリ | 247,244 KB |
実行使用メモリ | 67,660 KB |
最終ジャッジ日時 | 2024-05-03 18:41:28 |
合計ジャッジ時間 | 11,592 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 46 ms
42,452 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 1 ms
6,944 KB |
testcase_06 | AC | 1 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 1 ms
6,944 KB |
testcase_09 | AC | 1 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 1 ms
6,940 KB |
testcase_13 | AC | 2 ms
6,940 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 1 ms
6,944 KB |
testcase_16 | AC | 1 ms
6,940 KB |
testcase_17 | AC | 1 ms
6,940 KB |
testcase_18 | AC | 1 ms
6,944 KB |
testcase_19 | AC | 1 ms
6,940 KB |
testcase_20 | AC | 1 ms
6,940 KB |
testcase_21 | AC | 1 ms
6,940 KB |
testcase_22 | AC | 1 ms
6,940 KB |
testcase_23 | AC | 2 ms
6,940 KB |
testcase_24 | AC | 1 ms
6,940 KB |
testcase_25 | AC | 2 ms
6,940 KB |
testcase_26 | AC | 2 ms
6,944 KB |
testcase_27 | AC | 2 ms
6,940 KB |
testcase_28 | AC | 2 ms
6,944 KB |
testcase_29 | AC | 1 ms
6,944 KB |
testcase_30 | AC | 1 ms
6,940 KB |
testcase_31 | AC | 1 ms
6,944 KB |
testcase_32 | AC | 2 ms
6,944 KB |
testcase_33 | AC | 2 ms
6,940 KB |
testcase_34 | AC | 60 ms
60,360 KB |
testcase_35 | AC | 2 ms
6,940 KB |
testcase_36 | AC | 2 ms
6,940 KB |
testcase_37 | AC | 1 ms
6,944 KB |
testcase_38 | AC | 2 ms
6,940 KB |
testcase_39 | AC | 2 ms
6,940 KB |
testcase_40 | AC | 76 ms
40,880 KB |
testcase_41 | AC | 67 ms
41,016 KB |
testcase_42 | AC | 39 ms
25,380 KB |
testcase_43 | AC | 54 ms
31,724 KB |
testcase_44 | AC | 76 ms
39,888 KB |
testcase_45 | AC | 75 ms
40,184 KB |
testcase_46 | AC | 64 ms
39,000 KB |
testcase_47 | AC | 37 ms
24,356 KB |
testcase_48 | AC | 51 ms
29,944 KB |
testcase_49 | AC | 65 ms
37,116 KB |
testcase_50 | AC | 63 ms
38,068 KB |
testcase_51 | AC | 41 ms
28,028 KB |
testcase_52 | AC | 58 ms
37,988 KB |
testcase_53 | AC | 68 ms
39,296 KB |
testcase_54 | AC | 39 ms
24,124 KB |
testcase_55 | AC | 182 ms
51,444 KB |
testcase_56 | AC | 137 ms
43,460 KB |
testcase_57 | AC | 151 ms
47,120 KB |
testcase_58 | AC | 198 ms
64,496 KB |
testcase_59 | AC | 153 ms
50,328 KB |
testcase_60 | AC | 127 ms
64,088 KB |
testcase_61 | AC | 189 ms
52,152 KB |
testcase_62 | AC | 232 ms
67,660 KB |
testcase_63 | AC | 184 ms
52,468 KB |
testcase_64 | AC | 109 ms
50,740 KB |
testcase_65 | AC | 89 ms
39,112 KB |
testcase_66 | AC | 101 ms
35,992 KB |
testcase_67 | AC | 111 ms
38,624 KB |
testcase_68 | AC | 250 ms
61,008 KB |
testcase_69 | AC | 154 ms
43,904 KB |
testcase_70 | AC | 232 ms
63,908 KB |
testcase_71 | AC | 71 ms
35,660 KB |
testcase_72 | AC | 158 ms
57,612 KB |
testcase_73 | AC | 208 ms
50,052 KB |
testcase_74 | AC | 193 ms
47,440 KB |
testcase_75 | AC | 34 ms
34,120 KB |
testcase_76 | AC | 30 ms
28,092 KB |
testcase_77 | AC | 136 ms
56,236 KB |
testcase_78 | AC | 165 ms
57,752 KB |
testcase_79 | AC | 22 ms
19,768 KB |
testcase_80 | AC | 24 ms
22,124 KB |
testcase_81 | AC | 39 ms
38,024 KB |
testcase_82 | AC | 51 ms
43,032 KB |
testcase_83 | AC | 59 ms
38,532 KB |
61_evil_bias_nocross_01.txt | AC | 75 ms
40,552 KB |
61_evil_bias_nocross_02.txt | AC | 65 ms
41,132 KB |
61_evil_bias_nocross_03.txt | AC | 37 ms
25,380 KB |
61_evil_bias_nocross_04.txt | AC | 52 ms
32,824 KB |
61_evil_bias_nocross_05.txt | AC | 63 ms
39,392 KB |
61_evil_bias_nocross_06.txt | AC | 70 ms
41,276 KB |
61_evil_bias_nocross_07.txt | AC | 42 ms
27,944 KB |
61_evil_bias_nocross_08.txt | AC | 59 ms
37,872 KB |
61_evil_bias_nocross_09.txt | AC | 61 ms
38,944 KB |
61_evil_bias_nocross_10.txt | AC | 39 ms
24,636 KB |
61_evil_bias_nocross_11.txt | AC | 46 ms
31,128 KB |
61_evil_bias_nocross_12.txt | AC | 63 ms
36,056 KB |
ソースコード
#ifndef LOCAL #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #endif #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,class u> void print(const pair<t,u>&p,int suc=1){ print(p.a,2); print(p.b,suc); } template<class t,class u> void print_offset(const pair<t,u>&p,ll off,int suc=1){ print(p.a+off,2); print(p.b+off,suc); } 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); } template<class T> void print_offset(const vector<T>&v,ll off,int suc=1){ rep(i,v.size()) print(v[i]+off,i==int(v.size())-1?suc:2); } template<class T,size_t N> void print(const array<T,N>&v,int suc=1){ rep(i,N) print(v[i],i==int(N)-1?suc:2); } string readString(){ string s; cin>>s; return s; } template<class T> T sq(const T& t){ return t*t; } void YES(bool ex=true){ cout<<"YES\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void NO(bool ex=true){ cout<<"NO\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void Yes(bool ex=true){ cout<<"Yes\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void No(bool ex=true){ cout<<"No\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } //#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 botbit(ull a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } int popcount(ull 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); } vc<ll> presum(const vi&a){ vc<ll> s(si(a)+1); rep(i,si(a))s[i+1]=s[i]+a[i]; return s; } //軽量 template<class t> struct scc{ const int n; const vvc<t>&g; vi ord,low,bl,st; int s,head; void dfs(int v){ ord[v]=low[v]=head++; st.pb(v); for(auto to:g[v]){ if(ord[to]==-1){ dfs(to); chmin(low[v],low[to]); }else if(bl[to]==-1) chmin(low[v],ord[to]); } if(ord[v]==low[v]){ int c=s++; while(1){ int a=st.back(); st.pop_back(); bl[a]=c; if(v==a)break; } } } scc(const vvc<t>&gg):n(gg.size()),g(gg), ord(n,-1),low(n,-1),bl(n,-1),s(0),head(0){ rep(i,n)if(ord[i]==-1) dfs(i); rep(i,n) bl[i]=s-1-bl[i]; } }; struct N{ const vc<pi>&xy; int head,sum; N(const vc<pi>&ini):xy(ini),head(0),sum(0){} int sub(int x,int y){ assert(xy[head].a<=x); assert(xy[head].b<=y); if(head+1<si(xy)){ chmin(x,xy[head+1].a); chmin(y,xy[head+1].b); return (x-xy[head].a)*(y-xy[head].b); }else return 0; } int getarea(int x,int y){ while(head+1<si(xy)&&xy[head+1].a<=x&&xy[head+1].b<=y){ sum+=sub(inf,inf); head++; } return sum+sub(x,y); } }; void slv(){ vi ns=readvi(3); int m;cin>>m; int n=accumulate(all(ns),2); vi vs[3]; { int used=0; rep(k,3){ vs[k].pb(n-2); rep(_,ns[k])vs[k].pb(used++); vs[k].pb(n-1); } } vvc<int> g(n); rep(k,3)rep(i,si(vs[k])-1)g[vs[k][i]].pb(vs[k][i+1]); vc<pi> es; rep(_,m){ int a,b;cin>>a>>b; a--;b--; if(a>b)swap(a,b); g[a].pb(b); g[b].pb(a); es.eb(a,b); } scc<int> s(g); vc<pi> tp(n); vi len(3); rep(k,3){ int pre=-1; for(auto v:vs[k]){ if(s.bl[v]!=pre)len[k]++; pre=s.bl[v]; tp[v]=pi(k,len[k]-1); } } vi mx[2],mn[2]; rep(k,2){ mx[k].resize(len[2],0); mn[k].resize(len[2],len[k]-1); } vc<pi> xy{pi(0,0),pi(len[0]-1,len[1]-1)}; for(auto [a,b]:es){ if(tp[a].a==tp[b].a)continue; if(tp[b].a<2){ assert(tp[a].a==0); assert(tp[b].a==1); xy.eb(tp[a].b,tp[b].b); }else{ assert(tp[a].a==0||tp[a].a==1); auto [k,i]=tp[a]; chmax(mx[k][tp[b].b],i); chmin(mn[k][tp[b].b],i); } } mkuni(xy); N RU(xy),RD(xy),LU(xy),LD(xy); rep(k,2){ rep(i,len[2]-1)chmax(mx[k][i+1],mx[k][i]); per(i,len[2]-1)chmin(mn[k][i],mn[k][i+1]); } int ans=0; rep(i,len[2]-1){ int l=mx[0][i],r=mn[0][i+1]; int d=mx[1][i],u=mn[1][i+1]; ans+=RU.getarea(r,u); ans-=RD.getarea(r,d); ans-=LU.getarea(l,u); ans+=LD.getarea(l,d); } print(ans); } signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); //int t;cin>>t;rep(_,t) slv(); }