QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #90805 | #4000. Dynamic Reachability | wangzhe_0477 | TL | 3ms | 5876kb | C++23 | 9.5kb | 2023-03-25 13:53:47 | 2023-03-25 13:53:48 |
Judging History
answer
/*
Source:
Prefinals Moscow Workshop 2022
Day 5: Division A Contest 3, Saturday, April 23, 2022
Problem:
G. Dynamic Reachability
*/
#include <bits/stdc++.h>
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = std::pair<int, int>;
namespace MyStuffs {
template <typename Compare, const int defaultDelta>
struct Range {
private:
struct I {
private:
int v;
const int d;
public:
constexpr I(const int &_v, const int _d): v(_v), d(_d) {}
constexpr void operator++() {v += d;}
constexpr bool operator!=(const I &_v) {return Compare()(v, _v.v);}
constexpr int& operator*() {return v;}
};
const int l, r, d;
public:
Range(const int &_l, const int &_r, const int &_d = defaultDelta): l(_l), r(_r), d(_d) {
#if _DEBUG
assert(Compare()(l, r));
#endif
}
constexpr I begin() {return I(l, d);}
constexpr I end() {return I(r, d);}
};
#define FOR(i, arg...) for (const int &i : Range<std::less_equal<int>, 1>(arg))
#define RFOR(i, arg...) for (const int &i : Range<std::greater_equal<int>, -1>(arg))
#ifdef _DEBUG
#define LOG(arg...) fprintf(stderr, arg)
#else
#define LOG(arg...)
#endif
namespace IO {
#ifdef _DEBUG
constexpr int MAX_SIZE = 1;
#else
constexpr int MAX_SIZE = 1 << 20;
#endif
class Reader {
private:
FILE *file;
char buff[MAX_SIZE], *p1, *p2;
int getchar() {
if (p1 == p2) p2 = (p1 = buff) + fread(buff, 1, MAX_SIZE, file);
return p1 == p2 ? EOF : *p1++;
}
public:
Reader(FILE *_file) {
file = _file;
p1 = p2 = buff;
}
Reader(const char* file_dir) {
file = std::fopen(file_dir, "r");
p1 = p2 = buff;
}
void Read() {}
template<typename... Args>
void Read(int &x, Args &...other) {
int f, ch;
x = f = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
if (f) x = -x;
Read(other...);
}
template<typename... Args>
void Read(long long &x, Args &...other) {
int f, ch;
x = f = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
if (f) x = -x;
Read(other...);
}
template<typename... Args>
void Read(__int128 &x, Args &...other) {
int f, ch;
x = f = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
if (f) x = -x;
Read(other...);
}
template<typename... Args>
void Read(double &x, Args &...other) {
int f, ch;
x = f = 0;
ch = getchar();
for (; !isdigit(ch); ch = getchar()) f ^= ch == '-';
for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
if (ch == '.') {
double e = 1;
for (ch = getchar(); isdigit(ch); ch = getchar())
x += (ch ^ 48) * (e *= .1);
}
if (f) x = -x;
Read(other...);
}
template<typename... Args>
void Read(char &ch, Args &...other) {
ch = getchar();
while (!isgraph(ch)) ch = getchar();
Read(other...);
}
template<typename... Args>
void Read(std::string &s, Args &...other) {
char ch;
s = "";
ch = getchar();
for (; !isgraph(ch);) ch = getchar();
for (; isgraph(ch); ch = getchar()) s += ch;
Read(other...);
}
template<typename... Args>
void Read(char* s, Args &...other) {
char ch;
ch = getchar();
while (!isgraph(ch)) ch = getchar();
for (; isgraph(ch); ch = getchar()) *s++ = ch;
*s = 0;
Read(other...);
}
};
}
IO::Reader reader(stdin);
constexpr ULL E(LD x, int y) {
while (y--) x *= 10;
return x;
}
constexpr ULL SIZE(LD x, int y) {return E(x, y) + 5;}
const int inf32 = E(1, 9) + 5;
const LL inf64 = E(1, 18) + 5;
}
using namespace MyStuffs;
const int B = 2;
int n, m, q, col[SIZE(1, 5)], eu[SIZE(1, 5)], ev[SIZE(1, 5)];
std::vector<PII> graph[SIZE(5, 4)];
struct Quest {int type, x, y;} quest[SIZE(1, 5)];
std::vector<int> _graph[SIZE(5, 4)];
int sp[SIZE(5, 4)], id[SIZE(5, 4)], tot;
bool spN[SIZE(5, 4)], spE[SIZE(1, 5)];
int topoId[SIZE(5, 4)], topoCnt, inDeg[SIZE(5, 4)];
std::bitset<605> b[SIZE(1, 5)], now[605];
std::stack<int> sta;
bool inSta[SIZE(5, 4)];
int bel[SIZE(5, 4)], sccCnt;
int dfn[SIZE(5, 4)], low[SIZE(5, 4)], dfsCnt;
std::function<void(int)> Tarjan = [](int u) {
dfn[u] = low[u] = ++dfsCnt;
sta.push(u);
inSta[u] = true;
for (const auto &[v, id] : graph[u]) {
if (col[id]) continue;
if (spE[id]) continue;
if (!dfn[v]) {
Tarjan(v);
low[u] = std::min(low[u], low[v]);
}
else if (inSta[v]) low[u] = std::min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
sccCnt++;
int x;
do {
x = sta.top();
sta.pop();
inSta[x] = false;
bel[x] = sccCnt;
} while (x != u);
}
};
int main() {
reader.Read(n, m, q);
FOR (i, 1, m) {
reader.Read(eu[i], ev[i]);
graph[eu[i]].push_back({ev[i], i});
}
FOR (i, 1, q) {
int type, x, y;
reader.Read(type);
if (type == 1) {
reader.Read(x);
quest[i] = {type, x, 0};
}
else {
reader.Read(x, y);
quest[i] = {type, x, y};
}
}
FOR (i, 1, q, B) {
LOG("Range = (%d %d)\n", i, std::min(q, i + B - 1));
tot = 0;
dfsCnt = 0;
sccCnt = 0;
topoCnt = 0;
while (sta.size()) sta.pop();
FOR (j, 1, m) spE[j] = 0;
FOR (j, 1, n) dfn[j] = spN[j] = 0;
FOR (j, i, std::min(q, i + B - 1)) {
if (quest[j].type == 1) {
spE[quest[j].x] = true;
spN[eu[quest[j].x]] = true;
spN[ev[quest[j].x]] = true;
}
else {
spN[quest[j].x] = true;
spN[quest[j].y] = true;
}
}
FOR (j, 1, n) if (!dfn[j]) Tarjan(j);
FOR (j, 1, n) LOG("bel[%d] = %d\n", j, bel[j]);
FOR (j, 1, sccCnt) {
inDeg[j] = 0;
b[j].reset();
_graph[j].clear();
}
FOR (j, 1, n) if (spN[j]) {
sp[id[j] = ++tot] = j;
b[bel[j]].set(id[j]);
}
FOR (u, 1, n) for (auto [v, id] : graph[u]) {
if (col[id]) continue;
if (spE[id]) continue;
if (bel[u] == bel[v]) continue;
_graph[bel[u]].push_back(bel[v]);
inDeg[bel[v]]++;
}
std::queue<int> que;
FOR (j, 1, sccCnt) if (!inDeg[j]) que.push(j);
while (que.size()) {
int u = que.front();
que.pop();
topoId[++topoCnt] = u;
for (const auto &v : _graph[u])
if (--inDeg[v] == 0)
que.push(v);
}
RFOR(j, sccCnt, 1) for (const auto &v : _graph[topoId[j]]) b[topoId[j]] |= b[v];
FOR (i, 1, sccCnt) FOR (j, 1, sccCnt) if (b[i][j]) LOG("~~~ %d %d\n", i, j);
FOR (j, i, std::min(q, i + B - 1)) {
if (quest[j].type == 1) col[quest[j].x] ^= 1;
else {
FOR (k, 1, tot) now[k] = b[bel[sp[k]]];
FOR (k, i, std::min(q, i + B - 1))
if (quest[k].type == 1 && !col[quest[k].x])
now[id[eu[quest[k].x]]].set(id[ev[quest[k].x]]);
std::bitset<605> rest;
rest.set();
rest.reset(id[quest[j].x]);
std::queue<int> que;
que.push(id[quest[j].x]);
while (que.size()) {
int u = que.front();
que.pop();
while (true) {
const auto &tmp = rest & now[u];
if (tmp.any()) {
int v = tmp._Find_first();
rest.reset(v);
que.push(v);
}
else break;
}
}
puts(rest[id[quest[j].y]] ? "NO" : "YES");
}
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 5876kb
input:
5 6 7 1 2 1 3 2 4 3 4 3 5 4 5 2 1 5 2 2 3 1 3 1 4 2 1 4 1 3 2 1 5
output:
YES NO NO YES
result:
ok 4 lines
Test #2:
score: -100
Time Limit Exceeded
input:
50000 100000 100000 36671 44121 25592 44321 13226 46463 13060 25694 14021 20087 22881 38333 34655 47774 22868 26462 31154 48710 27491 32365 5874 47497 17622 28600 1886 14193 22315 23656 14973 22704 1335 25384 22612 34915 2852 48213 23334 25519 24342 28784 6238 36125 14598 39494 33069 34250 2123 3059...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...