QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#527024#5504. Flower Gardennhuang685RE 3439ms324788kbC++235.9kb2024-08-22 07:39:472024-08-22 07:39:47

Judging History

你现在查看的是最新测评结果

  • [2024-08-22 07:39:47]
  • 评测
  • 测评结果:RE
  • 用时:3439ms
  • 内存:324788kb
  • [2024-08-22 07:39:47]
  • 提交

answer

/**
 * @author n685
 * @brief
 * @date 2024-08-21 17:05:01
 *
 *
 */
#include "bits/stdc++.h"

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420

void nline() {}

void bar() {}

void start_clock() {}

void end_clock() {}
#endif

void tarjan(
  int node,
  std::vector<int> &clr,
  std::vector<int> &dfn,
  int n,
  const std::vector<std::vector<int>> &adj
) {
  static int cnt = 0, num = 0;
  static std::vector<int> low(n, -1);
  static std::vector<bool> vis(n);
  static std::stack<int, std::vector<int>> st;
  dfn[node] = cnt++;
  low[node] = dfn[node];
  st.push(node);
  vis[node] = true;
  for (int i : adj[node]) {
    if (dfn[i] == -1) {
      tarjan(i, clr, dfn, n, adj);
    }
    if (vis[i]) {
      low[node] = std::min(low[node], low[i]);
    }
  }
  if (dfn[node] == low[node]) {
    while (!st.empty()) {
      int v = st.top();
      st.pop();
      clr[v] = num;
      vis[v] = false;
      if (node == v) {
        break;
      }
    }
    ++num;
  }
}

std::vector<int> scc(int n, const std::vector<std::vector<int>> &adj) {
  std::vector<int> clr(n, -1), dfn(n, -1);
  for (int i = 0; i < n; ++i) {
    if (dfn[i] == -1) {
      tarjan(i, clr, dfn, n, adj);
    }
  }
  return clr;
}

std::optional<std::vector<bool>> type1(
  int n,
  int thres,
  const std::vector<int> &sz,
  const std::vector<std::vector<int>> &adj,
  const std::vector<std::vector<int>> &radj
) {
  std::vector<int> in(n);
  std::queue<int> q;
  for (int i = 0; i < n; ++i) {
    in[i] = static_cast<int>(adj[i].size());
    if (in[i] == 0) {
      q.push(i);
    }
  }
  std::vector<bool> ans(n);
  int sum = 0;
  while (!q.empty()) {
    int node = q.front();
    q.pop();
    if (sz[node] >= thres) {
      continue;
    }
    sum += sz[node];
    ans[node] = true;
    if (sum >= thres) {
      return ans;
    }
    for (int i : radj[node]) {
      if (--in[i] == 0) {
        q.push(i);
      }
    }
  }
  return std::nullopt;
}

int dfs_type2(
  int node,
  std::vector<bool> &ans,
  const std::vector<int> &sz,
  const std::vector<std::vector<int>> &adj
) {
  int res = sz[node];
  ans[node] = true;
  for (int i : adj[node]) {
    if (!ans[i]) {
      res += dfs_type2(i, ans, sz, adj);
    }
  }
  return res;
}

std::optional<std::vector<bool>> type2(
  int n,
  int thres,
  const std::vector<int> &sz,
  const std::vector<std::vector<int>> &adj
) {
  for (int i = 0; i < n; ++i) {
    if (sz[i] >= thres) {
      std::vector<bool> ans(n);
      if (dfs_type2(i, ans, sz, adj) <= 2 * thres) {
        return ans;
      }
    }
  }
  return std::nullopt;
}

void build(
  int node,
  int l,
  int r,
  int &sz,
  std::vector<int> &iin,
  std::vector<int> &iout,
  std::vector<std::vector<int>> &adj
) {
  if (l == r) {
    iin[node] = l;
    iout[node] = l;
    return;
  }
  iin[node] = sz++;
  iout[node] = sz++;
  adj.emplace_back();
  adj.emplace_back();
  int mid = (l + r) / 2;
  build(2 * node, l, mid, sz, iin, iout, adj);
  build(2 * node + 1, mid + 1, r, sz, iin, iout, adj);
  adj[iin[node]].push_back(iin[2 * node]);
  adj[iin[node]].push_back(iin[2 * node + 1]);
  adj[iout[2 * node]].push_back(iout[node]);
  adj[iout[2 * node + 1]].push_back(iout[node]);
}

enum class Dir : int8_t { IN, OUT };

void unite(
  int a,
  int b,
  int v,
  Dir dir,
  int node,
  int l,
  int r,
  std::vector<std::vector<int>> &adj,
  const std::vector<int> &iin,
  const std::vector<int> &iout
) {
  if (a <= l && r <= b) {
    if (dir == Dir::OUT) {
      adj[iout[node]].push_back(v);
    } else {
      adj[v].push_back(iin[node]);
    }
    return;
  }
  int mid = (l + r) / 2;
  if (a <= mid) {
    unite(a, b, v, dir, 2 * node, l, mid, adj, iin, iout);
  }
  if (b > mid) {
    unite(a, b, v, dir, 2 * node + 1, mid + 1, r, adj, iin, iout);
  }
}

void solve() {
  int n, q;
  std::cin >> n >> q;

  int bound = static_cast<int>(std::bit_ceil<uint32_t>(3 * n));

  std::vector<int> iin(2 * bound), iout(2 * bound);
  int cnt = bound;
  std::vector<std::vector<int>> adj(bound);
  build(1, 0, bound - 1, cnt, iin, iout, adj);
  for (int i = 0; i < q; ++i) {
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;
    --a;
    --b;
    --c;
    --d;
    adj.emplace_back();
    unite(a, b, cnt + i, Dir::OUT, 1, 0, bound - 1, adj, iin, iout);
    unite(c, d, cnt + i, Dir::IN, 1, 0, bound - 1, adj, iin, iout);
  }
  std::vector<int> clr = scc(cnt + q, adj);
  int m = *std::ranges::max_element(clr) + 1;
  std::vector<int> sz(m);
  std::vector<std::vector<int>> sadj(m);
  std::vector<std::vector<int>> gr(m);
  for (int i = 0; i < cnt + q; ++i) {
    if (i < 3 * n) {
      ++sz[clr[i]];
      gr[clr[i]].push_back(i);
    }
    for (int j : adj[i]) {
      if (clr[i] != clr[j]) {
        sadj[clr[i]].push_back(clr[j]);
      }
    }
  }
  for (std::vector<int> &v : sadj) {
    std::ranges::sort(v);
    v.erase(std::unique(v.begin(), v.end()), v.end());
  }
  std::vector<std::vector<int>> sradj(m);
  for (int i = 0; i < m; ++i) {
    for (int j : sadj[i]) {
      sradj[j].push_back(i);
    }
  }

  std::optional<std::vector<bool>> opt = type1(m, n, sz, sadj, sradj);
  std::vector<bool> ans;
  if (opt.has_value()) {
    ans = *opt;
  } else {
    opt = type2(m, n, sz, sadj);
    if (opt.has_value()) {
      ans = *opt;
    } else {
      std::cout << "NIE\n";
      return;
    }
  }
  std::cout << "TAK\n";
  std::string val(3 * n, 'R');
  for (int i = 0; i < m; ++i) {
    if (ans[i]) {
      for (int j : gr[i]) {
        val[j] = 'F';
      }
    }
  }
  std::cout << val << '\n';
}

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  int z;
  std::cin >> z;
  for (int i = 0; i < z; ++i) {
    dbg(i + 1);
    solve();
    bar();
  }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

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: 3170ms
memory: 159132kb

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: 0
Accepted
time: 3439ms
memory: 324788kb

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:

ok good!

Test #4:

score: 0
Accepted
time: 3149ms
memory: 291076kb

input:

10
33333 100000
2646 2646 6430 6446
82226 82231 15128 15132
877 877 85831 88474
51389 79196 37573 37573
38030 38030 14248 14280
63032 68489 81074 81074
46468 46468 7403 7487
19864 20058 97979 97979
71640 71833 8558 8558
12121 12434 82481 82481
32901 32901 1899 2162
65312 77886 75969 75974
87983 8798...

output:

TAK
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFRRFFFFRFFRRFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

result:

ok good!

Test #5:

score: -100
Runtime Error

input:

87005
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
1 1
1 3 2 3
1 2
1 1 2 2
2 2 1 1
1 2
1 3 1 1
1 1 1 3
4 20
3 5 6 12
4 5 7 11
1 1 2 2
3 4 7 12
3 5 10 10
3 5 8 8
4 4 9 11
4 4 7 7
1 1 9 10
3 4 6 9
3 5 11 12
3 3 7 9
3 5 2 2
4 5 2 2
1 1 7 11
1 1 10 10
3 5 7 8
4 4 2 2
1 1 2 2
4 5 8 10
4 12
11 ...

output:


result: