結果

問題 No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
ユーザー hashiryohashiryo
提出日時 2024-02-18 20:09:34
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 25 ms / 5,000 ms
コード長 5,297 bytes
コンパイル時間 2,643 ms
コンパイル使用メモリ 215,696 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-09-29 00:54:23
合計ジャッジ時間 3,874 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// clang-format off
std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10
    ),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
std::ostream&operator<<(std::ostream&os,const __uint128_t &v){if(!v)os<<"0";__uint128_t tmp=v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return
    std::reverse(s.begin(),s.end()),os<<s;}
#define checkpoint() (void(0))
#define debug(...) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
#include <type_traits>
#define _LR(name, IT, CT) \
template <class T> struct name { \
using Iterator= typename std::vector<T>::IT; \
Iterator bg, ed; \
Iterator begin() const { return bg; } \
Iterator end() const { return ed; } \
size_t size() const { return std::distance(bg, ed); } \
CT &operator[](int i) const { return bg[i]; } \
}
_LR(ListRange, iterator, const T);
_LR(ConstListRange, const_iterator, const T);
#undef _LR
template <class T> struct CSRArray {
std::vector<T> dat;
std::vector<int> p;
size_t size() const { return p.size() - 1; }
ListRange<T> operator[](int i) { return {dat.begin() + p[i], dat.begin() + p[i + 1]}; }
ConstListRange<T> operator[](int i) const { return {dat.cbegin() + p[i], dat.cbegin() + p[i + 1]}; }
};
template <template <class> class F, class T> std::enable_if_t<std::disjunction_v<std::is_same<F<T>, ListRange<T>>, std::is_same<F<T>, ConstListRange
    <T>>, std::is_same<F<T>, CSRArray<T>>>, std::ostream &> operator<<(std::ostream &os, const F<T> &r) {
os << '[';
for (int _= 0, __= r.size(); _ < __; ++_) os << (_ ? ", " : "") << r[_];
return os << ']';
}
class DulmageMendelsohn {
std::vector<int> blg[2], mate[2], pos[2];
std::vector<std::array<int, 2>> es;
public:
DulmageMendelsohn(int L, int R): blg{std::vector(L, -3), std::vector(R, -3)} {}
void add_edge(int l, int r) { es.push_back({l, r}); }
void build() {
const int n[]= {(int)blg[0].size(), (int)blg[1].size()};
std::vector<int> g[2], rt, pre, que(std::max(n[0], n[1]));
for (int b= 2; b--;) g[b].resize(es.size()), pos[b].resize(n[b] + 1), mate[b].assign(n[b], -1);
for (auto [l, r]: es) ++pos[0][l], ++pos[1][r];
for (int b= 2; b--;) std::partial_sum(pos[b].begin(), pos[b].end(), pos[b].begin());
for (auto [l, r]: es) g[0][--pos[0][l]]= r, g[1][--pos[1][r]]= l;
int t= 0, k= 0;
for (bool upd= true; upd; t= 0) {
upd= false, rt.assign(n[0], -1), pre.assign(n[0], -1);
for (int l= n[0]; l--;)
if (mate[0][l] == -1) que[t++]= rt[l]= pre[l]= l;
for (int i= 0; i < t; ++i)
if (int l= que[i]; mate[0][rt[l]] == -1)
for (int j= pos[0][l], r, nl; j < pos[0][l + 1]; ++j) {
if (nl= mate[1][r= g[0][j]]; nl == -1) {
for (upd= true; r != -1; l= pre[l]) mate[1][r]= l, std::swap(mate[0][l], r);
break;
}
if (pre[nl] == -1) rt[que[t++]= nl]= rt[pre[nl]= l];
}
}
for (int s= n[0], v; s--;)
if (rt[s] != -1)
if (blg[0][s]= -1, v= mate[0][s]; v != -1) blg[1][v]= -1;
for (int s= n[1]; s--;)
if (mate[1][s] == -1) blg[1][que[t++]= s]= 0;
for (int i= 0; i < t; ++i)
for (int v= que[i], j= pos[1][v], u, w; j < pos[1][v + 1]; ++j)
if (blg[0][u= g[1][j]] == -3)
if (w= mate[0][u], blg[0][u]= 0; w != -1 && blg[1][w] == -3) blg[1][que[t++]= w]= 0;
pre.assign(pos[0].begin(), pos[0].begin() + n[0]), t= 0;
for (int s= n[0], v; s--;)
if (blg[0][s] == -3)
for (blg[0][v= s]= -4; v >= 0;) {
if (pre[v] == pos[0][v + 1]) rt[t++]= v, v= blg[0][v];
else if (int w= mate[1][g[0][pre[v]++]]; blg[0][w] == -3) blg[0][w]= v, v= w;
}
for (int i= 0, e= 0; t--;)
if (int s= rt[t], p= mate[0][s]; blg[1][p] == -3)
for (que[e++]= p, blg[0][s]= blg[1][p]= ++k; i < e; ++i)
for (int v= que[i], j= pos[1][v]; j < pos[1][v + 1]; ++j)
if (int u= g[1][j], w= mate[0][u]; blg[1][w] == -3) que[e++]= w, blg[0][u]= blg[1][w]= k;
++k;
for (int b= 2, s; b--;) {
for (pos[b].assign(k + 2, 0), s= n[b]; s--; ++pos[b][blg[b][s]])
if (blg[b][s] == -1) blg[b][s]= k;
for (std::partial_sum(pos[b].begin(), pos[b].end(), pos[b].begin()), s= n[b]; s--;) mate[b][--pos[b][blg[b][s]]]= s;
}
}
int component_num() const { return pos[0].size() - 1; }
int left_belong(int l) const { return blg[0][l]; }
int right_belong(int r) const { return blg[1][r]; }
ConstListRange<int> left_block(int k) const { return {mate[0].cbegin() + pos[0][k], mate[0].cbegin() + pos[0][k + 1]}; }
ConstListRange<int> right_block(int k) const { return {mate[1].cbegin() + pos[1][k], mate[1].cbegin() + pos[1][k + 1]}; }
};
using namespace std;
signed main() {
cin.tie(0);
ios::sync_with_stdio(0);
int N, M, L;
cin >> N >> M >> L;
DulmageMendelsohn dm(N, M);
int S[L], T[L];
for (int i= 0; i < L; ++i) {
cin >> S[i] >> T[i];
dm.add_edge(--S[i], --T[i]);
}
dm.build();
int k= dm.component_num();
for (int i= 0; i < L; ++i) {
int l= dm.left_belong(S[i]), r= dm.right_belong(T[i]);
cout << (l != r || l == 0 || r == k - 1 || dm.left_block(l).size() >= 2 ? "Yes" : "No") << '\n';
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0