QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#522284 | #5504. Flower Garden | Z_drj | WA | 1216ms | 297288kb | C++14 | 4.2kb | 2024-08-16 20:55:17 | 2024-08-16 20:55:17 |
Judging History
answer
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <algorithm>
using i64 = long long;
const int N = 2E6 + 5;
int n, q;
bool tag[N];
std::vector<int> g[N], G[N], rG[N];
#define ls(u) u << 1
#define rs(u) u << 1 | 1
struct SegmentTree {
struct Segment {
int l, r;
Segment(int _l = 0, int _r = 0) : l(_l), r(_r) {}
}s[N];
int rtin, rtout;
int tot;
int ID[N];
void buildin(int &u, int l, int r) {
u = ++tot;
if (l == r) {
ID[l] = u, tag[u] = true;
return;
}
int mid = l + r >> 1;
buildin(s[u].l, l, mid), buildin(s[u].r, mid + 1, r);
g[u].push_back(s[u].l), g[u].push_back(s[u].r);
}
void buildout(int &u, int l, int r) {
if (l == r) {
u = ID[l];
return;
}
u = ++tot;
int mid = l + r >> 1;
buildout(s[u].l, l, mid), buildout(s[u].r, mid + 1, r);
g[s[u].l].push_back(u), g[s[u].r].push_back(u);
}
void modifyin(int u, int l, int r, int ql, int qr, int x) {
if (ql <= l && r <= qr) {
g[ID[x]].push_back(u);
return;
}
int mid = l + r >> 1;
if (ql <= mid) {modifyin(s[u].l, l, mid, ql, qr, x);}
if (qr > mid) {modifyin(s[u].r, mid + 1, r, ql, qr, x);}
}
void modifyout(int u, int l, int r, int ql, int qr, int x) {
if (ql <= l && r <= qr) {
g[u].push_back(ID[x]);
return;
}
int mid = l + r >> 1;
if (ql <= mid) {modifyout(s[u].l, l, mid, ql, qr, x);}
if (qr > mid) {modifyout(s[u].r, mid + 1, r, ql, qr, x);}
}
void clear() {
tot = 0;
}
}t;
#undef ls
#undef rs
int dfn_cnt, scc_cnt;
int dfn[N], low[N];
int col[N], siz[N];
std::stack<int> s;
bool vis[N];
void tarjan(int u) {
s.push(u); vis[u] = true;
low[u] = dfn[u] = ++dfn_cnt;
for (auto v : g[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = std::min(low[u], low[v]);
} else if (vis[v]) {
low[u] = std::min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
++scc_cnt;
int x;
do {
x = s.top(); s.pop();
vis[x] = false;
col[x] = scc_cnt;
siz[scc_cnt] += tag[x];
} while (x != u);
}
}
int cnt;
void dfs(int u) {
if (vis[u]) return;
vis[u] = true, cnt += siz[u];
for (auto v : G[u]) {
dfs(v);
}
}
int in[N];
bool Topo() {
memset(vis, 0, sizeof(vis));
std::queue<int> q;
for (int i = 1; i <= scc_cnt; i++) {
if (!in[i]) {
q.push(i);
}
}
cnt = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
if (cnt + siz[u] > 2 * n) continue;
vis[u] = true;
if ((cnt += siz[u]) >= n) {
return true;
}
for (auto v : rG[u]) {
if (--in[v]) {
q.push(v);
}
}
}
return false;
}
void clear() {
for (int i = 1; i <= t.tot; i++) {
g[i].clear(), G[i].clear(), rG[i].clear();
}
dfn_cnt = scc_cnt = 0;
memset(dfn, 0, sizeof(dfn)), memset(low, 0, sizeof(low));
memset(col, 0, sizeof(col)), memset(siz, 0, sizeof(siz));
memset(vis, 0, sizeof(vis)), memset(in, 0, sizeof(in));
memset(tag, 0, sizeof(tag));
t.clear();
}
void solve() {
scanf("%d %d", &n, &q);
t.buildin(t.rtin, 1, n * 3), t.buildout(t.rtout, 1, n * 3);
for (int i = 1; i <= q; i++) {
int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
int v = ++t.tot;
t.modifyout(t.rtout, 1, n * 3, a, b, v), t.modifyin(t.rtin, 1, n * 3, c, d, v);
}
for (int i = 1; i <= t.tot; i++) {
if (!dfn[i]) {
tarjan(i);
}
}
for (int i = 1; i <= t.tot; i++) {
for (auto v : g[i]) {
if (col[i] != col[v]) {
G[col[i]].push_back(col[v]);
rG[col[v]].push_back(col[i]);
++in[col[i]];
}
}
}
for (int i = 1; i <= scc_cnt; i++) {
if (siz[i] >= n) {
memset(vis + 1, 0, sizeof(bool) * scc_cnt);
cnt = 0; dfs(i);
if (cnt <= 2 * n) {
puts("TAK");
for (int j = 1; j <= t.tot; j++) {
if (tag[j]) {
printf("%c", vis[col[j]]? 'F': 'R');
}
}
puts("");
return;
}
}
}
puts("NIE");
// if (!Topo()) {
// puts("NIE");
// } else {
// puts("TAK");
// for (int i = 1; i <= t.tot; i++) {
// if (tag[i]) {
// printf("%c", vis[col[i]]? 'F': 'R');
// }
// }
// puts("");
// }
}
int main() {
int T; scanf("%d", &T);
while (T--) {
solve();
clear();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 26ms
memory: 206708kb
input:
2 1 3 1 1 2 2 1 2 3 3 1 1 3 3 1 3 1 1 2 2 2 2 3 3 3 3 1 1
output:
TAK RRF NIE
result:
ok good!
Test #2:
score: 0
Accepted
time: 1216ms
memory: 297288kb
input:
10 33333 100000 28701 40192 93418 95143 95902 97908 78378 78461 36823 44196 22268 23996 23977 24786 33315 48829 83965 90411 4923 8445 20235 21177 32543 47454 29598 35414 72477 73049 2014 12632 42163 46466 64305 65518 98825 99552 32331 41625 92772 96224 26500 54122 76990 77126 18249 20335 31165 36080...
output:
NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE
result:
ok good!
Test #3:
score: -100
Wrong Answer
time: 1081ms
memory: 273580kb
input:
10 33333 100000 15207 33614 66276 66276 97173 97173 67589 73960 19673 36626 65207 65207 89825 98169 27079 27079 56067 56966 7560 7560 18170 35477 18752 18752 32621 36748 34460 34460 61595 61700 14117 14117 32395 36710 9064 9064 13172 13172 1728 4640 40462 41878 47171 47171 76965 82414 5767 5767 9225...
output:
TAK FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...
result:
wrong answer zla odpowiedz!