QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #99197 | #5504. Flower Garden | Johnsonloy | Compile Error | / | / | C++14 | 12.3kb | 2023-04-21 16:49:32 | 2023-04-21 16:49:35 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-04-21 16:49:35]
- 评测
- 测评结果：Compile Error
- 用时：0ms
- 内存：0kb
- [2023-04-21 16:49:32]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
const int maxn = 4e6 + 10;
namespace IO {
void openfile() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
}
inline int read() {
int x = 0, f = 0;
char c = getchar();
while (!isdigit(c))
f |= c == '-', c = getchar();
while (isdigit(c))
x = x * 10 + c - '0', c = getchar();
if (f)
x = -x;
return x;
}
} // namespace IO
using namespace IO;
int tot, n, m;
int rt1, rt2, top, cnt, tim;
int dfn[maxn], low[maxn], bl[maxn], vis[maxn], sta[maxn];
int x[maxn], y[maxn], bian, in[maxn], sz[maxn], ans[maxn];
vector<int> e[maxn], g[maxn], pos[maxn];
void add(int xx, int yy) {
e[xx].push_back(yy);
x[++bian] = xx, y[bian] = yy;
}
struct node {
int l, r, ls, rs;
} t[maxn];
void build1(int& rt, int l, int r) {
if (!rt)
rt = ++tot;
t[rt] = {l, r};
if (l == r)
return;
int mid = (l + r) >> 1;
build1(t[rt].ls, l, mid), build1(t[rt].rs, mid + 1, r);
add(rt, t[rt].ls), add(rt, t[rt].rs);
}
void build2(int& rt, int l, int r) {
if (!rt)
rt = ++tot;
t[rt] = {l, r};
if (l == r)
return add(rt - rt2 + 1, rt), void();
int mid = (l + r) >> 1;
build2(t[rt].ls, l, mid), build2(t[rt].rs, mid + 1, r);
add(t[rt].ls, rt), add(t[rt].rs, rt);
}
void init() {
for (int i = 1; i <= tot; i++)
t[i] = {0, 0, 0, 0}, dfn[i] = low[i] = bl[i] = in[i] = sz[i] = vis[i] = 0, e[i].clear(),
g[i].clear(), pos[i].clear();
tot = tim = bian = cnt = top = rt1 = rt2 = 0;
}
void jia1(int rt, int l, int r, int x, int y, int d) {
if (x <= l && r <= y)
return add(d, rt), void();
int mid = (l + r) >> 1;
if (x <= mid)
jia1(t[rt].ls, l, mid, x, y, d);
if (mid < y)
jia1(t[rt].rs, mid + 1, r, x, y, d);
}
void jia2(int rt, int l, int r, int x, int y, int d) {
if (x <= l && r <= y)
return add(rt, d), void();
int mid = (l + r) >> 1;
if (x <= mid)
jia2(t[rt].ls, l, mid, x, y, d);
if (mid < y)
jia2(t[rt].rs, mid + 1, r, x, y, d);
}
void tarjan(int x) {
vis[x] = 1, sta[++top] = x;
low[x] = dfn[x] = ++tim;
for (auto v : e[x]) {
if (!dfn[v])
tarjan(v), low[x] = min(low[x], low[v]);
else if (vis[v])
low[x] = min(low[x], dfn[v]);
}
if (dfn[x] == low[x]) {
int y;
cnt++;
do {
y = sta[top--];
vis[y] = 0;
bl[y] = cnt;
} while (x != y);
}
}
void topo() {
queue<int> q;
for (int i = 1; i <= cnt; i++)
if (!in[i])
q.push(i);
while (!q.empty()) {
int x = q.front();
q.pop();
sta[++top] = x;
for (auto v : e[x]) {
in[v]--;
if (!in[v])
q.push(v);
}
}
}
void dfs(int x) {
vis[x] = 1;
for (auto v : e[x])
if (!vis[v])
dfs(v);
}
void topo2(int x) {
queue<int> q;
q.push(x);
while (!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 1;
for (auto v : g[x])
if (!vis[v])
q.push(v);
}
}
void solve() {
n = read(), m = read();
build1(rt1, 1, n * 3), build2(rt2, 1, n * 3);
for (int i = 1; i <= m; i++) {
int l1 = read(), r1 = read(), l2 = read(), r2 = read();
int d1 = ++tot;
jia2(rt2, 1, n * 3, l1, r1, d1), jia1(rt1, 1, n * 3, l2, r2, d1);
}
for (int i = 1; i <= tot; i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= tot; i++)
e[i].clear(), g[i].clear();
for (int i = 1; i <= bian; i++) {
if (bl[x[i]] == bl[y[i]])
continue;
e[bl[x[i]]].push_back(bl[y[i]]);
g[bl[y[i]]].push_back(bl[x[i]]);
in[bl[y[i]]]++;
}
for (int i = 1; i < rt2; i++)
if (t[i].l == t[i].r)
++sz[bl[i]], pos[bl[i]].push_back(t[i].l);
topo();
int sum = 0, flag = 0;
for (int i = 1; i <= top; i++) {
sum += sz[i];
if (sum >= n && sum <= n * 2) {
flag = i;
break;
}
}
if (flag) {
for (int i = 1; i <= top; i++)
for (auto v : pos[i])
ans[v] = (i <= flag);
puts("TAK");
for (int i = 1; i <= n * 3; i++)
if (ans[i])
putchar('F');
else
putchar('R');
puts("");
return;
}
for (int i = 1; i <= top; i++)
if (sz[i] >= n) {
for (int i = 1; i <= top; i++)
vis[i] = 0;
dfs(i);
sum = 0;
for (int i = 1; i <= top; i++)
if (vis[i])
sum += sz[i];
if (sum >= n && sum <= n * 2) {
for (int i = 1; i <= top; i++)
for (auto v : pos[i])
ans[v] = vis[i];
puts("TAK");
for (int i = 1; i <= n * 3; ++i)
if (ans[i])
putchar('F');
else
putchar('R');
puts("");
return;
}
for (int i = 1; i <= top; i++)
vis[i] = 0;
topo2(i), sum = 0;
for (int i = 1; i <= top; i++)
if (vis[i])
sum += sz[i];
if (sum >= n && sum <= n * 2) {
for (int i = 1; i <= top; i++)
for (auto v : pos[i])
ans[v] = vis[i];
puts("TAK");
for (int i = 1; i <= n * 3; ++i)
if (ans[i])
putchar('F');
else
putchar('R');
puts("");
return;
}
}
puts("NIE");
}
signed main() {
openfile();
int T = read();
while (T--)
init(), solve();
return 0;
}
/*
1
5 2
5 7 12 13
6 13 1 11
*/#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
const int maxn = 2e6 + 10;
namespace IO {
void openfile() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
}
inline int read() {
int x = 0, f = 0;
char c = getchar();
while (!isdigit(c))
f |= c == '-', c = getchar();
while (isdigit(c))
x = x * 10 + c - '0', c = getchar();
if (f)
x = -x;
return x;
}
} // namespace IO
using namespace IO;
int tot, n, m;
int rt1, rt2;
int dfn[maxn], low[maxn], tim, vis[maxn], sta[maxn], top, cnt, bl[maxn];
int x[maxn], y[maxn], bian, in[maxn], sz[maxn], ans[maxn];
vector<int> e[maxn], g[maxn], pos[maxn];
void add(int xx, int yy) {
e[xx].push_back(yy);
// cout << xx << ' ' << yy << endl;
g[yy].push_back(xx);
x[++bian] = xx, y[bian] = yy;
}
struct node {
int l, r, ls, rs;
} t[maxn];
void build1(int& rt, int l, int r) {
if (!rt)
rt = ++tot;
t[rt] = {l, r};
if (l == r)
return;
int mid = (l + r) >> 1;
build1(t[rt].ls, l, mid), build1(t[rt].rs, mid + 1, r);
add(rt, t[rt].ls), add(rt, t[rt].rs);
}
void build2(int& rt, int l, int r) {
if (!rt)
rt = ++tot;
t[rt] = {l, r};
if (l == r)
return add(rt - rt2 + 1, rt), void();
int mid = (l + r) >> 1;
build2(t[rt].ls, l, mid), build2(t[rt].rs, mid + 1, r);
add(t[rt].ls, rt), add(t[rt].rs, rt);
}
void init() {
for (int i = 1; i <= tot; i++)
t[i] = {0, 0, 0, 0}, dfn[i] = low[i] = bl[i] = in[i] = sz[i] = vis[i] = 0, e[i].clear(),
g[i].clear(), pos[i].clear();
tot = tim = bian = cnt = top = rt1 = rt2 = 0;
}
void jia1(int rt, int l, int r, int x, int y, int d) {
if (x <= l && r <= y)
return add(d, rt), void();
int mid = (l + r) >> 1;
if (x <= mid)
jia1(t[rt].ls, l, mid, x, y, d);
if (mid < y)
jia1(t[rt].rs, mid + 1, r, x, y, d);
}
void jia2(int rt, int l, int r, int x, int y, int d) {
if (x <= l && r <= y)
return add(rt, d), void();
int mid = (l + r) >> 1;
if (x <= mid)
jia2(t[rt].ls, l, mid, x, y, d);
if (mid < y)
jia2(t[rt].rs, mid + 1, r, x, y, d);
}
void tarjan(int x) {
vis[x] = 1, sta[++top] = x;
low[x] = dfn[x] = ++tim;
for (auto v : e[x]) {
if (!dfn[v])
tarjan(v), low[x] = min(low[x], low[v]);
else if (vis[v])
low[x] = min(low[x], dfn[v]);
}
if (dfn[x] == low[x]) {
int y;
cnt++;
do {
y = sta[top--];
vis[y] = 0;
bl[y] = cnt;
} while (x != y);
}
}
void topo() {
queue<int> q;
for (int i = 1; i <= cnt; i++)
if (!in[i])
q.push(i);
while (!q.empty()) {
int x = q.front();
q.pop();
sta[++top] = x;
for (auto v : e[x]) {
in[v]--;
if (!in[v])
q.push(v);
}
}
}
void dfs(int x) {
vis[x] = 1;
for (auto v : e[x])
if (!vis[v])
dfs(v);
}
void dfs2(int x) {
vis[x] = 0;
for (auto v : g[x])
if (vis[v])
dfs2(v);
}
void solve() {
n = read(), m = read();
build1(rt1, 1, n * 3), build2(rt2, 1, n * 3);
for (int i = 1; i <= m; i++) {
int l1 = read(), r1 = read(), l2 = read(), r2 = read();
int d1 = ++tot;
jia2(rt2, 1, n * 3, l1, r1, d1), jia1(rt1, 1, n * 3, l2, r2, d1);
}
for (int i = 1; i <= tot; i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= tot; i++)
e[i].clear(), g[i].clear();
for (int i = 1; i <= bian; i++) {
if (bl[x[i]] == bl[y[i]])
continue;
e[bl[x[i]]].push_back(bl[y[i]]);
in[bl[y[i]]]++;
}
for (int i = 1; i < rt2; i++)
if (t[i].l == t[i].r)
++sz[bl[i]], pos[bl[i]].push_back(t[i].l);
topo();
int sum = 0, flag = 0;
for (int i = 1; i <= top; i++) {
sum += sz[i];
if (sum >= n && sum <= n * 2) {
flag = i;
break;
}
}
if (flag) {
for (int i = 1; i <= top; i++)
for (auto v : pos[i])
ans[v] = (i <= flag);
puts("TAK");
for (int i = 1; i <= n * 3; i++)
if (ans[i])
putchar('F');
else
putchar('R');
puts("");
return;
}
for (int i = 1; i <= top; i++)
if (sz[i] >= n) {
for (int i = 1; i <= n; i++)
vis[i] = 0;
dfs(i);
int sum = 0;
for (int i = 1; i <= top; i++)
if (vis[i])
sum += sz[i];
if (sum >= n && sum <= n * 2) {
for (int i = 1; i <= top; i++)
for (auto v : pos[i])
ans[v] = vis[i];
puts("TAK");
for (int i = 1; i <= n * 3; ++i)
if (ans[i])
putchar('F');
else
putchar('R');
puts("");
return;
}
for (int i = 1; i <= n; i++)
vis[i] = 1;
dfs2(i), sum = 0;
for (int i = 1; i <= top; i++)
if (vis[i])
sum += sz[i];
if (sum >= n && sum <= n * 2) {
for (int i = 1; i <= top; i++)
for (auto v : pos[i])
ans[v] = vis[i];
puts("TAK");
for (int i = 1; i <= n * 3; ++i)
if (ans[i])
putchar('F');
else
putchar('R');
puts("");
return;
}
}
puts("NIE");
}
signed main() {
openfile();
int T = read();
while (T--)
init(), solve();
return 0;
}
详细
answer.code:261:11: error: redefinition of ‘const int maxn’
261 | const int maxn = 2e6 + 10;
| ^~~~
answer.code:6:11: note: ‘const int maxn’ previously defined here
6 | const int maxn = 4e6 + 10;
| ^~~~
answer.code:264:6: error: redefinition of ‘void IO::openfile()’
264 | void openfile() {
| ^~~~~~~~
answer.code:9:6: note: ‘void IO::openfile()’ previously defined here
9 | void openfile() {
| ^~~~~~~~
answer.code:271:12: error: redefinition of ‘int IO::read()’
271 | inline int read() {
| ^~~~
answer.code:16:12: note: ‘int IO::read()’ previously defined here
16 | inline int read() {
| ^~~~
answer.code:285:5: error: redefinition of ‘int tot’
285 | int tot, n, m;
| ^~~
answer.code:30:5: note: ‘int tot’ previously declared here
30 | int tot, n, m;
| ^~~
answer.code:285:10: error: redefinition of ‘int n’
285 | int tot, n, m;
| ^
answer.code:30:10: note: ‘int n’ previously declared here
30 | int tot, n, m;
| ^
answer.code:285:13: error: redefinition of ‘int m’
285 | int tot, n, m;
| ^
answer.code:30:13: note: ‘int m’ previously declared here
30 | int tot, n, m;
| ^
answer.code:286:5: error: redefinition of ‘int rt1’
286 | int rt1, rt2;
| ^~~
answer.code:31:5: note: ‘int rt1’ previously declared here
31 | int rt1, rt2, top, cnt, tim;
| ^~~
answer.code:286:10: error: redefinition of ‘int rt2’
286 | int rt1, rt2;
| ^~~
answer.code:31:10: note: ‘int rt2’ previously declared here
31 | int rt1, rt2, top, cnt, tim;
| ^~~
answer.code:287:5: error: redefinition of ‘int dfn [4000010]’
287 | int dfn[maxn], low[maxn], tim, vis[maxn], sta[maxn], top, cnt, bl[maxn];
| ^~~
answer.code:32:5: note: ‘int dfn [4000010]’ previously declared here
32 | int dfn[maxn], low[maxn], bl[maxn], vis[maxn], sta[maxn];
| ^~~
answer.code:287:16: error: redefinition of ‘int low [4000010]’
287 | int dfn[maxn], low[maxn], tim, vis[maxn], sta[maxn], top, cnt, bl[maxn];
| ^~~
answer.code:32:16: note: ‘int low [4000010]’ previously declared here
32 | int dfn[maxn], low[maxn], bl[maxn], vis[maxn], sta[maxn];
| ^~~
answer.code:287:27: error: redefinition of ‘int tim’
287 | int dfn[maxn], low[maxn], tim, vis[maxn], sta[maxn], top, cnt, bl[maxn];
| ^~~
answer.code:31:25: note: ‘int tim’ previously declared here
31 | int rt1, rt2, top, cnt, tim;
| ^~~
answer.code:287:32: error: redefinition of ‘int vis [4000010]’
287 | int dfn[maxn], low[maxn], tim, vis[maxn], sta[maxn], top, cnt, bl[maxn];
| ^~~
answer.code:32:37: note: ‘int vis [4000010]’ previously declared here
32 | int dfn[maxn], low[maxn], bl[maxn], vis[maxn], sta[maxn];
| ^~~
answer.code:287:43: error: redefinition of ‘int sta [4000010]’
287 | int dfn[maxn], low[maxn], tim, vis[maxn], sta[maxn], top, cnt, bl[maxn];
| ^~~
answer.code:32:48: note: ‘int sta [4000010]’ previously declared here
32 | int dfn[maxn], low[maxn], bl[maxn], vis[maxn], sta[maxn];
| ^~~
answer.code:287:54: error: redefinition of ‘int top’
287 | int dfn[maxn], low[maxn], tim, vis[maxn], sta[maxn], top, cnt, bl[maxn];
| ^~~
answer.code:31:15: note: ‘int top’ previously declared here
31 | int rt1, rt2, top, cnt, tim;
| ^~~
answer.code:287:59: error: redefinition of ‘int cnt’
287 | int dfn[maxn], low[maxn], tim, vis[maxn], sta[maxn], top, cnt, bl[maxn];
| ^~~
answer.code:31:20: note: ‘int cnt’ previously declared here
31 | int rt1, rt2, top, cnt, tim;
| ^~~
answer.code:287:64: error: redefinition of ‘int bl [4000010]’
287 | int dfn[maxn], low[maxn], tim, vis[maxn], sta[maxn], top, cnt, bl[maxn];
| ^~
answer.code:32:27: note: ‘int bl [4000010]’ previously declared here
32 | int dfn[maxn], low[maxn], bl[maxn], vis[maxn], sta[maxn];
| ^~
answer.code:288:5: error: redefinition of ‘int x [4000010]’
288 | int x[maxn], y[maxn], bian, in[maxn], sz[maxn], ans[maxn];
| ^
answer.code:33:5: note: ‘int x [4000010]’ previously declared here
33 | int x[maxn], y[maxn], bian, in[maxn], sz[maxn], ans[maxn];
| ^
answer.code:288:14: error: redefinition of ‘int y [4000010]’
288 | int x[maxn], y[maxn], bian, in[maxn], sz[maxn], ans[maxn];
| ^
answer.code:33:14: note: ‘int y [4000010]’ previously declared here
33 | int x[maxn], y[maxn], bian, in[...