結果
問題 | No.2160 みたりのDominator |
ユーザー | snuke |
提出日時 | 2022-12-11 11:13:32 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 461 ms / 2,000 ms |
コード長 | 4,968 bytes |
コンパイル時間 | 2,752 ms |
コンパイル使用メモリ | 221,748 KB |
実行使用メモリ | 67,372 KB |
最終ジャッジ日時 | 2024-10-15 08:36:35 |
合計ジャッジ時間 | 16,857 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 119 ms
62,512 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 2 ms
5,248 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 2 ms
5,248 KB |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | AC | 2 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
testcase_21 | AC | 2 ms
5,248 KB |
testcase_22 | AC | 2 ms
5,248 KB |
testcase_23 | AC | 2 ms
5,248 KB |
testcase_24 | AC | 2 ms
5,248 KB |
testcase_25 | AC | 2 ms
5,248 KB |
testcase_26 | AC | 3 ms
5,248 KB |
testcase_27 | AC | 2 ms
5,248 KB |
testcase_28 | AC | 2 ms
5,248 KB |
testcase_29 | AC | 2 ms
5,248 KB |
testcase_30 | AC | 2 ms
5,248 KB |
testcase_31 | AC | 2 ms
5,248 KB |
testcase_32 | AC | 2 ms
5,248 KB |
testcase_33 | AC | 2 ms
5,248 KB |
testcase_34 | AC | 129 ms
67,372 KB |
testcase_35 | AC | 2 ms
5,248 KB |
testcase_36 | AC | 2 ms
5,248 KB |
testcase_37 | AC | 2 ms
5,248 KB |
testcase_38 | AC | 2 ms
5,248 KB |
testcase_39 | AC | 2 ms
5,248 KB |
testcase_40 | AC | 165 ms
56,104 KB |
testcase_41 | AC | 149 ms
56,272 KB |
testcase_42 | AC | 89 ms
34,968 KB |
testcase_43 | AC | 128 ms
43,160 KB |
testcase_44 | AC | 160 ms
54,328 KB |
testcase_45 | AC | 160 ms
51,996 KB |
testcase_46 | AC | 141 ms
49,476 KB |
testcase_47 | AC | 82 ms
29,084 KB |
testcase_48 | AC | 111 ms
34,776 KB |
testcase_49 | AC | 134 ms
42,436 KB |
testcase_50 | AC | 128 ms
42,504 KB |
testcase_51 | AC | 102 ms
38,400 KB |
testcase_52 | AC | 142 ms
51,680 KB |
testcase_53 | AC | 162 ms
53,676 KB |
testcase_54 | AC | 89 ms
33,912 KB |
testcase_55 | AC | 414 ms
41,560 KB |
testcase_56 | AC | 284 ms
36,948 KB |
testcase_57 | AC | 336 ms
38,504 KB |
testcase_58 | AC | 420 ms
52,888 KB |
testcase_59 | AC | 362 ms
42,636 KB |
testcase_60 | AC | 214 ms
54,684 KB |
testcase_61 | AC | 382 ms
39,640 KB |
testcase_62 | AC | 461 ms
55,064 KB |
testcase_63 | AC | 405 ms
43,244 KB |
testcase_64 | AC | 168 ms
43,360 KB |
testcase_65 | AC | 199 ms
35,264 KB |
testcase_66 | AC | 218 ms
29,868 KB |
testcase_67 | AC | 225 ms
31,440 KB |
testcase_68 | AC | 447 ms
48,300 KB |
testcase_69 | AC | 309 ms
36,868 KB |
testcase_70 | AC | 445 ms
49,480 KB |
testcase_71 | AC | 153 ms
32,932 KB |
testcase_72 | AC | 313 ms
49,216 KB |
testcase_73 | AC | 428 ms
40,884 KB |
testcase_74 | AC | 408 ms
38,424 KB |
testcase_75 | AC | 54 ms
34,604 KB |
testcase_76 | AC | 44 ms
28,132 KB |
testcase_77 | AC | 245 ms
50,264 KB |
testcase_78 | AC | 295 ms
50,748 KB |
testcase_79 | AC | 33 ms
19,608 KB |
testcase_80 | AC | 41 ms
22,484 KB |
testcase_81 | AC | 73 ms
40,232 KB |
testcase_82 | AC | 85 ms
43,072 KB |
testcase_83 | AC | 112 ms
37,780 KB |
61_evil_bias_nocross_01.txt | AC | 161 ms
56,144 KB |
61_evil_bias_nocross_02.txt | AC | 148 ms
56,396 KB |
61_evil_bias_nocross_03.txt | AC | 86 ms
34,964 KB |
61_evil_bias_nocross_04.txt | AC | 118 ms
43,160 KB |
61_evil_bias_nocross_05.txt | AC | 157 ms
54,328 KB |
61_evil_bias_nocross_06.txt | AC | 164 ms
56,448 KB |
61_evil_bias_nocross_07.txt | AC | 104 ms
38,400 KB |
61_evil_bias_nocross_08.txt | AC | 142 ms
51,684 KB |
61_evil_bias_nocross_09.txt | AC | 150 ms
53,808 KB |
61_evil_bias_nocross_10.txt | AC | 91 ms
33,908 KB |
61_evil_bias_nocross_11.txt | AC | 126 ms
42,492 KB |
61_evil_bias_nocross_12.txt | AC | 143 ms
48,480 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < (n); ++i) #define rep1(i,n) for(int i = 1; i <= (n); ++i) #define drep(i,n) for(int i = (n)-1; i >= 0; --i) #define srep(i,s,t) for (int i = s; i < (t); ++i) #define rng(a) a.begin(),a.end() #define rrng(a) a.rbegin(),a.rend() #define fi first #define se second #define pb push_back #define eb emplace_back #define pob pop_back #define sz(x) (int)(x).size() #define pcnt __builtin_popcountll #define snuke srand((unsigned)clock()+(unsigned)time(NULL)); #define newline puts("") using namespace std; template<typename T> using vc = vector<T>; template<typename T> using vv = vc<vc<T>>; template<typename T> using PQ = priority_queue<T,vc<T>,greater<T>>; using uint = unsigned; using ull = unsigned long long; using vi = vc<int>; using vvi = vv<int>; using vvvi = vv<vi>; using ll = long long; using vl = vc<ll>; using vvl = vv<ll>; using vvvl = vv<vl>; using P = pair<int,int>; using vp = vc<P>; using vvp = vv<P>; int geti(){int x;scanf("%d",&x);return x;} vi pm(int n, int s=0) { vi a(n); iota(rng(a),s); return a;} template<typename T>istream& operator>>(istream&i,vc<T>&v){rep(j,sz(v))i>>v[j];return i;} template<typename T>string join(const T&v,const string& d=""){stringstream s;rep(i,sz(v))(i?s<<d:s)<<v[i];return s.str();} template<typename T>ostream& operator<<(ostream&o,const vc<T>&v){if(sz(v))o<<join(v," ");return o;} template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v){return i>>v.fi>>v.se;} template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v){return o<<v.fi<<","<<v.se;} template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int){a.fi--;a.se--;} template<typename T>void operator--(vc<T>&a,int){for(T&x:a)x--;} template<typename T>void operator++(vc<T>&a,int){for(T&x:a)x++;} template<typename T>void operator+=(vc<T>&a,T b){for(T&x:a)x+=b;} template<typename T>void operator+=(vc<T>&a,const vc<T>&b){a.insert(a.end(),rng(b));} template<typename T1,typename T2>bool mins(T1& x,const T2&y){if(x>y){x=y;return true;}else return false;} template<typename T1,typename T2>bool maxs(T1& x,const T2&y){if(x<y){x=y;return true;}else return false;} template<typename Tx, typename Ty>Tx dup(Tx x, Ty y){return (x+y-1)/y;} template<typename T>ll suma(const vc<T>&a){ll res(0);for(auto&&x:a)res+=x;return res;} template<typename T>ll suma(const vv<T>&a){ll res(0);for(auto&&x:a)res+=suma(x);return res;} template<typename T>void uni(T& a){sort(rng(a)); a.erase(unique(rng(a)),a.end());} template<typename T>void prepend(vc<T>&a,const T&x){a.insert(a.begin(),x);} const double eps = 1e-10; const ll LINF = 1001002003004005006ll; const int INF = 1001001001; #define dame { puts("-1"); return;} #define yes { puts("Yes"); return;} #define no { puts("No"); return;} #define ret(x) { cout<<(x)<<endl; return;} #define yn {puts("Yes");}else{puts("No");} const int MX = 200005; // SCC // upstream is smaller id struct scc { int n, k; vvi to, ot, d, gt; // to, rev_to, groups, group_to vi g, used, kv; // group, gomi, topo_ord scc(int n=0):n(n),to(n),ot(n){} int inc() { to.pb(vi()); ot.pb(vi()); return n++;} void add(int a, int b) { to[a].pb(b); ot[b].pb(a);} void dfs(int v) { if (used[v]) return; used[v] = 1; rep(i,sz(to[v])) dfs(to[v][i]); kv[--k] = v; } void rfs(int v) { if (g[v] != -1) return; g[v] = k; d[k].pb(v); rep(i,sz(ot[v])) rfs(ot[v][i]); } void init() { k = n; used = kv = vi(n); g = vi(n,-1); rep(i,n) dfs(i); rep(i,n) if (g[kv[i]] == -1) { d.pb(vi()); rfs(kv[i]); k++; } } }; // struct Solver { void solve() { const int K = 3, K2 = 1<<K; vi n(K); int m; cin>>n>>m; int sv = suma(n), tv = sv+1; scc g(tv+1); { int v = 0; rep(i,K) { int p = sv; rep(j,n[i]) { g.add(p,v); p = v; v++; } g.add(p,tv); } } rep(i,m) { int a,b; scanf("%d%d",&a,&b); --a; --b; g.add(a,b); g.add(b,a); } g.init(); vvi a(K); { int v = 0; rep(i,K) { a[i].pb(g.g[sv]); rep(j,n[i]) { a[i].pb(g.g[v]); v++; } a[i].pb(g.g[tv]); uni(a[i]); } } ll ans = 0; vl dp(K2); dp[0] = 1; { vi as; rep(i,K) as += a[i]; uni(as); as.pob(); vi is(K); for (int na : as) { int x = 0; rep(i,K) if (a[i][is[i]] == na) { is[i]++; x |= 1<<i; } drep(s,K2) { if (s&x) { if ((s&x) != x) dp[s] = 0; } else { for (int t = x; t; t = (t-1)&x) dp[s|t] += dp[s]; } } } ans = dp[K2-1]; } cout<<ans<<endl; } }; int main() { // cin.tie(nullptr); ios::sync_with_stdio(false); int ts = 1; // scanf("%d",&ts); rep1(ti,ts) { Solver solver; solver.solve(); } return 0; }