結果
問題 | No.8122 How Many Liars Are There? |
ユーザー |
👑 |
提出日時 | 2025-04-01 23:03:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 285 ms / 2,000 ms |
コード長 | 5,228 bytes |
コンパイル時間 | 1,903 ms |
コンパイル使用メモリ | 127,488 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-04-01 23:03:21 |
合計ジャッジ時間 | 7,401 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 65 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:168:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 168 | scanf("%d", &P[u]); | ~~~~~^~~~~~~~~~~~~ main.cpp:173:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 173 | scanf("%d", &A[u]); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include <cassert> #include <cmath> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <bitset> #include <chrono> #include <complex> #include <deque> #include <functional> #include <iostream> #include <limits> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <sstream> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; using Int = long long; template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; } template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } #define COLOR(s) ("\x1b[" s "m") struct Functional { int n; vector<int> par; int cyclesLen; vector<int> lens; vector<vector<int>> cycles; // cycle id or -1 vector<int> on; // forest vector<vector<int>> graph; int zeit; vector<int> dis, fin, dep; // root is cycle[k][l] vector<int> ks, ls; Functional() {} Functional(const vector<int> &par_) : par(par_) { n = par.size(); for (int u = 0; u < n; ++u) { assert(0 <= par[u]); assert(par[u] < n); } cycles.clear(); vector<int> vis(n, -1); for (int s = 0; s < n; ++s) { int u = s; for (; !~vis[u]; u = par[u]) { vis[u] = s; } if (vis[u] == s) { vector<int> cycle; for (int v = u; ; ) { cycle.push_back(v); if ((v = par[v]) == u) break; } cycles.push_back(cycle); } } cyclesLen = cycles.size(); lens.resize(cyclesLen); on.assign(n, -1); for (int k = 0; k < cyclesLen; ++k) { lens[k] = cycles[k].size(); for (const int u : cycles[k]) { on[u] = k; } } graph.assign(n, {}); for (int u = 0; u < n; ++u) if (!~on[u]) { graph[par[u]].push_back(u); } zeit = 0; dis.assign(n, -1); fin.assign(n, -1); dep.assign(n, 0); ks.assign(n, -1); ls.assign(n, -1); for (int k = 0; k < cyclesLen; ++k) { for (int l = 0; l < lens[k]; ++l) { dfs(k, l, cycles[k][l]); } } } void dfs(int k, int l, int u) { dis[u] = zeit++; ks[u] = k; ls[u] = l; for (const int v : graph[u]) { dep[v] = dep[u] + 1; dfs(k, l, v); } fin[u] = zeit; } // min d s.t. f^d(u) = v, or -1 int dist(int u, int v) const { if (ks[u] != ks[v]) return -1; if (~on[v]) { int dl = ls[v] - ls[u]; if (dl < 0) dl += lens[ks[u]]; return dep[u] + dl; } return (dis[v] <= dis[u] && dis[u] < fin[v]) ? (dep[u] - dep[v]) : -1; }; }; //////////////////////////////////////////////////////////////////////////////// // \sum[u] f[u] + \sum[u] (f[u] xor f[P[u]] xor A[u]) = K int N, K; vector<int> P; vector<int> A; Functional F; using BS = bitset<2010>; BS dp[1010][2]; BS mul(BS fs, BS gs) { BS hs; for (int k = fs._Find_first(); k < (int)fs.size(); k = fs._Find_next(k)) { hs |= gs << k; } return hs; } void dfs(int u) { for (int x = 0; x < 2; ++x) { dp[u][x].reset(); dp[u][x].set(x); } for (const int v : F.graph[u]) { dfs(v); for (int x = 0; x < 2; ++x) { BS tmp; for (int y = 0; y < 2; ++y) { tmp |= mul(dp[u][x], dp[v][y] << (x ^ y ^ A[v])); } dp[u][x] = tmp; } } // for(int x=0;x<2;++x){cerr<<"dp["<<u<<"]["<<x<<"] = ";for(int k=0;k<=2*N;++k)cerr<<dp[u][x][k];cerr<<endl;} } int main() { for (; ~scanf("%d%d", &N, &K); ) { P.resize(N); for (int u = 0; u < N; ++u) { scanf("%d", &P[u]); --P[u]; } A.resize(N); for (int u = 0; u < N; ++u) { scanf("%d", &A[u]); } K = 2*N - K; F = Functional(P); // cerr<<"cycles = "<<F.cycles<<endl; memset(dp, 0, sizeof(dp)); BS ans; ans.set(0); for (int k = 0; k < F.cyclesLen; ++k) { const int len = F.lens[k]; const auto &us = F.cycles[k]; for (int l = 0; l < len; ++l) { dfs(us[l]); } BS here; for (int s = 0; s < 2; ++s) { BS crt[2] = {}; crt[s] = dp[us[0]][s]; for (int l = 1; l < len; ++l) { BS nxt[2] = {}; for (int x = 0; x < 2; ++x) for (int y = 0; y < 2; ++y) { nxt[y] |= mul(crt[x], dp[us[l]][y] << (x ^ y ^ A[us[l - 1]])); } for (int x = 0; x < 2; ++x) crt[x] = nxt[x]; } for (int x = 0; x < 2; ++x) { here |= crt[x] << (x ^ s ^ A[us[len - 1]]); } } ans = mul(ans, here); } // cerr<<"ans = ";for(int k=0;k<=2*N;++k)cerr<<ans[k];cerr<<endl; puts(ans[K] ? "Yes" : "No"); } return 0; }