QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#99197#5504. Flower GardenJohnsonloyCompile Error//C++1412.3kb2023-04-21 16:49:322023-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]
  • 评测
  • [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[...