結果
問題 | No.943 取り調べ |
ユーザー | otamay6 |
提出日時 | 2019-12-06 08:34:39 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,034 bytes |
コンパイル時間 | 2,802 ms |
コンパイル使用メモリ | 181,236 KB |
実行使用メモリ | 4,504 KB |
最終ジャッジ日時 | 2023-08-24 19:42:47 |
合計ジャッジ時間 | 3,543 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | WA | - |
testcase_04 | AC | 82 ms
4,380 KB |
testcase_05 | AC | 82 ms
4,380 KB |
testcase_06 | AC | 83 ms
4,380 KB |
testcase_07 | WA | - |
testcase_08 | AC | 83 ms
4,380 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | AC | 1 ms
4,376 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | AC | 1 ms
4,380 KB |
testcase_19 | WA | - |
testcase_20 | AC | 2 ms
4,380 KB |
testcase_21 | AC | 1 ms
4,376 KB |
testcase_22 | AC | 22 ms
4,384 KB |
testcase_23 | AC | 83 ms
4,380 KB |
ソースコード
#include<bits/stdc++.h> #define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i) #define rep(i,a,b) for(int i=int(a);i<int(b);++i) #define All(x) (x).begin(),(x).end() using namespace std; using ll = long long; using Graph =vector<vector<int>>; void visit(const Graph &g, int v, vector< vector<int> >& scc, stack<int> &S, vector<bool> &inS, vector<int> &low, vector<int> &num, int& time) { low[v] = num[v] = ++time; S.push(v); inS[v] = true; for(auto e: g[v]) { int w = e; if (num[w] == 0) { visit(g, w, scc, S, inS, low, num, time); low[v] = min(low[v], low[w]); } else if (inS[w]) low[v] = min(low[v], num[w]); } if (low[v] == num[v]) { scc.push_back(vector<int>()); while (1) { int w = S.top(); S.pop(); inS[w] = false; scc.back().push_back(w); if (v == w) break; } } } void stronglyConnectedComponents(const Graph& g, vector< vector<int> >& scc) { const int n = g.size(); vector<int> num(n), low(n); stack<int> S; vector<bool> inS(n); int time = 0; REP(u, n) if (num[u] == 0) visit(g, u, scc, S, inS, low, num, time); } int main(){ int N;cin>>N; vector<vector<int>> X(N,vector<int>(N)),graph(N); REP(i,N) REP(j,N){ cin>>X[i][j]; if(X[i][j]) graph[i].push_back(j); } vector<int> A(N); REP(i, N){ cin >> A[i]; } int ans=INT_MAX; vector<vector<int>> scc; stronglyConnectedComponents(graph,scc); vector<vector<bool>> B(N,vector<bool>(N,false)); REP(bit,1<<N){ int res=0; REP(j,N) if(bit>>j&1){ res+=A[j]; } bool flag=true; REP(i,N) if(~bit>>i&1){ rep(j,i+1,N) if((~bit>>j&1)&&X[i][j]){ if(X[j][i]) flag=false; } } REP(i,scc.size()){ bool ok=false; for(auto e:scc[i]){ if(bit>>e&1) ok=true; } if(!ok) flag=false; } if(flag) ans=min(ans,res); } cout<<ans<<endl; }