結果
問題 | No.2160 みたりのDominator |
ユーザー | snuke |
提出日時 | 2022-12-11 11:09:35 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,894 bytes |
コンパイル時間 | 2,687 ms |
コンパイル使用メモリ | 223,196 KB |
実行使用メモリ | 67,376 KB |
最終ジャッジ日時 | 2024-10-15 08:31:37 |
合計ジャッジ時間 | 18,216 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 122 ms
62,644 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 | 3 ms
5,248 KB |
testcase_24 | AC | 2 ms
5,248 KB |
testcase_25 | AC | 2 ms
5,248 KB |
testcase_26 | AC | 2 ms
5,248 KB |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | AC | 2 ms
5,248 KB |
testcase_34 | AC | 113 ms
67,376 KB |
testcase_35 | WA | - |
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 | WA | - |
testcase_40 | AC | 165 ms
56,064 KB |
testcase_41 | AC | 151 ms
56,196 KB |
testcase_42 | AC | 90 ms
34,972 KB |
testcase_43 | AC | 124 ms
43,156 KB |
testcase_44 | AC | 157 ms
54,320 KB |
testcase_45 | AC | 158 ms
51,952 KB |
testcase_46 | AC | 140 ms
49,472 KB |
testcase_47 | AC | 80 ms
28,956 KB |
testcase_48 | AC | 112 ms
34,776 KB |
testcase_49 | AC | 131 ms
42,312 KB |
testcase_50 | AC | 123 ms
42,476 KB |
testcase_51 | AC | 95 ms
39,448 KB |
testcase_52 | AC | 140 ms
51,684 KB |
testcase_53 | AC | 151 ms
54,012 KB |
testcase_54 | AC | 84 ms
34,300 KB |
testcase_55 | WA | - |
testcase_56 | AC | 253 ms
36,948 KB |
testcase_57 | AC | 292 ms
38,500 KB |
testcase_58 | WA | - |
testcase_59 | WA | - |
testcase_60 | AC | 210 ms
54,684 KB |
testcase_61 | AC | 383 ms
39,760 KB |
testcase_62 | WA | - |
testcase_63 | AC | 363 ms
43,248 KB |
testcase_64 | AC | 163 ms
43,488 KB |
testcase_65 | WA | - |
testcase_66 | WA | - |
testcase_67 | WA | - |
testcase_68 | WA | - |
testcase_69 | WA | - |
testcase_70 | WA | - |
testcase_71 | WA | - |
testcase_72 | AC | 301 ms
49,220 KB |
testcase_73 | WA | - |
testcase_74 | WA | - |
testcase_75 | AC | 54 ms
34,364 KB |
testcase_76 | AC | 44 ms
28,132 KB |
testcase_77 | WA | - |
testcase_78 | WA | - |
testcase_79 | AC | 33 ms
19,612 KB |
testcase_80 | AC | 39 ms
22,608 KB |
testcase_81 | AC | 71 ms
40,232 KB |
testcase_82 | AC | 83 ms
43,196 KB |
testcase_83 | WA | - |
61_evil_bias_nocross_01.txt | AC | 160 ms
56,264 KB |
61_evil_bias_nocross_02.txt | AC | 147 ms
56,268 KB |
61_evil_bias_nocross_03.txt | AC | 86 ms
35,612 KB |
61_evil_bias_nocross_04.txt | AC | 116 ms
43,252 KB |
61_evil_bias_nocross_05.txt | AC | 157 ms
54,344 KB |
61_evil_bias_nocross_06.txt | AC | 158 ms
56,556 KB |
61_evil_bias_nocross_07.txt | AC | 100 ms
39,324 KB |
61_evil_bias_nocross_08.txt | AC | 138 ms
51,668 KB |
61_evil_bias_nocross_09.txt | AC | 145 ms
53,612 KB |
61_evil_bias_nocross_10.txt | AC | 93 ms
35,196 KB |
61_evil_bias_nocross_11.txt | AC | 119 ms
42,260 KB |
61_evil_bias_nocross_12.txt | AC | 136 ms
48,484 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() { vi n(3); int m; cin>>n>>m; int sv = suma(n), tv = sv+1; scc g(tv+1); { int v = 0; rep(i,3) { 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(3); { int v = 0; rep(i,3) { a[i].pb(g.g[sv]); rep(j,n[i]) { a[i].pb(g.g[v]); v++; } uni(a[i]); } } ll ans = 0; vl dp(8); dp[0] = 1; { vi as; rep(i,3) as += a[i]; uni(as); vi is(3); for (int na : as) { int x = 0; rep(i,3) if (a[i][is[i]] == na) { is[i]++; x |= 1<<i; } drep(s,8) { 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[7]; } 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; }