QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#99026#5504. Flower GardenKHINRE 8ms37404kbC++145.3kb2023-04-21 08:57:542023-04-21 08:57:56

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 08:57:56]
  • 评测
  • 测评结果:RE
  • 用时:8ms
  • 内存:37404kb
  • [2023-04-21 08:57:54]
  • 提交

answer

# include <cstdlib>
# include <cstring>
# include <vector>
# include <algorithm>
# include <iostream>
# include <istream>
# include <ostream>

namespace khin {
  using namespace std;
  namespace ucup {
    inline namespace source {}
    namespace ucup1 {
      namespace stage03 {
        namespace f { void main(); }
      }
    }
  }
}

int main() { khin::ucup::ucup1::stage03::f::main(); }

namespace khin::ucup::ucup1::stage03::f {
  namespace test_case {
    constexpr uint n_max(33'333), q_max(100'000);
    inline uint next_index();
    inline void set(uint, uint);
    inline void add(uint, uint);
    class segment_tree {
      constexpr static uint lg_max = __lg(3 * n_max + 1) + 1;
      uint lg, s[1 << (lg_max + 1)], t[1 << (lg_max + 1)];
      public:
      segment_tree() {}
      void assign(uint const n) {
        lg = __lg(3 * n + 1) + 1;
        for (uint i(0); i != 1u << lg; ++i) {
          s[1 << lg | i] = next_index();
          t[1 << lg | i] = next_index();
          if (1 <= i && i <= 3 * n) set(s[1 << lg | i], 1);
          add(t[1 << lg | i], s[1 << lg | i]);
        }
        for (uint i((1u << lg) - 1); i; --i) {
          s[i] = next_index(), t[i] = next_index();
          add(s[i << 1 | 0], s[i]), add(s[i << 1 | 1], s[i]);
          add(t[i], t[i << 1 | 0]), add(t[i], t[i << 1 | 1]);
        }
      }
      void adds(uint l, uint r, uint const x) const {
        --l |= 1 << lg, ++r |= 1 << lg;
        while ((l ^ r) >> 1) {
          if ((l & 1) == 0) add(s[l ^ 1], x);
          if ((r & 1) == 1) add(s[r ^ 1], x);
          l >>= 1, r >>= 1;
        }
      }
      void addt(uint l, uint r, uint const x) const {
        --l |= 1 << lg, ++r |= 1 << lg;
        while ((l ^ r) >> 1) {
          if ((l & 1) == 0) add(x, t[l ^ 1]);
          if ((r & 1) == 1) add(x, t[r ^ 1]);
          l >>= 1, r >>= 1;
        }
      }
      void addr(uint const a, uint const b, uint const c, uint const d) const
      { uint const x(next_index()); adds(a, b, x), addt(c, d, x); }
    };
    class graph {
      constexpr static uint v_max
        = 2 * (1 << (__lg(3 * n_max + 1) + 1)) + q_max;
      struct vertex0 { vector<uint> t; uint index, low, scc; uint val; };
      struct vertex1 { vector<uint> s, t; uint sum; bool vis; };
      vertex0 v0[v_max]; uint p, index, num; vertex1 v1[v_max + 1];
      void tarjan(uint const x) {
        static uint stk[2 * (1 << (__lg(n_max + 1) + 1)) + q_max], *top(stk);
        v0[x].low = v0[x].index = ++index, *top++ = x;
        for (uint const t : v0[x].t)
          if (!v0[t].index) tarjan(t), v0[x].low = min(v0[x].low, v0[t].low);
          else if (!v0[t].scc) v0[x].low = min(v0[x].low, v0[t].index);
        if (v0[x].low == v0[x].index)
        { ++num; while (v0[*--top].scc = num, *top != x); }
      }
      uint sums(uint const x) {
        if (v1[x].vis) return 0; else v1[x].vis = true;
        uint res(v1[x].sum);
        for (uint const s : v1[x].s) res += sums(s);
        return res;
      }
      uint sumt(uint const x) {
        if (v1[x].vis) return 0; else v1[x].vis = true;
        uint res(v1[x].sum);
        for (uint const t : v1[x].t) res += sumt(t);
        return res;
      }
      public:
      void clear() {
        fill(v0, v0 + p, vertex0());
        fill(v1 + 1, v1 + num + 1, vertex1());
        num = index = p = 0;
      }
      uint next_index() { return p++; }
      void set(uint const x, uint const v) { this->v0[x].val = v; }
      void add(uint const s, uint const t) { v0[s].t.push_back(t); }
      string solve(uint const n) {
        for (uint i(0); i < p; ++i) if (!v0[i].index) tarjan(i);
        for (uint i(0); i < p; ++i) v1[v0[i].scc].sum += v0[i].val;
        uint tot(0);
        for (uint i(1); i <= num; ++i)
          if ((tot += v1[i].sum) >= n && tot <= 2 * n) {
            string s(3 * n, ' ');
            for (uint j(1); j <= 3 * n; ++j)
              s[j - 1] = v0[j << 1 | 0].scc <= i ? 'F' : 'R';
            return s;
          }
        for (uint i(1); i <= num; ++i) if (v1[i].sum > n) {
          if (sums(i) <= 2 * n) {
            string s(3 * n, ' ');
            for (uint j(1); j <= 3 * n; ++j)
              s[j - 1] = v1[v0[j << 1 | 0].scc].vis ? 'F' : 'R';
            for (uint j(1); j <= num; ++j) v1[j].vis = false;
            return s;
          }
          for (uint j(1); j <= num; ++j) v1[j].vis = false;
          if (sumt(i) <= 2 * n) {
            string s(3 * n, ' ');
            for (uint j(1); j <= 3 * n; ++j)
              s[j - 1] = v1[v0[j << 1 | 0].scc].vis ? 'F' : 'R';
            for (uint j(1); j <= num; ++j) v1[j].vis = false;
            return s;
          }
          for (uint j(1); j <= num; ++j) v1[j].vis = false;
        }
        return string();
      }
    };
    uint n, q; segment_tree seg; graph g;
    inline uint next_index() { return g.next_index(); }
    inline void set(uint const x, uint const v) { g.set(x, v); }
    inline void add(uint const s, uint const t) { g.add(s, t); }
    void main() {
      cin >> n >> q, seg.assign(n);
      for (uint i(0); i < q; ++i) {
        uint a, b, c, d;
        cin >> a >> b >> c >> d;
        seg.addr(a, b, c, d);
      }
      string const ans(g.solve(n));
      if (ans.empty()) cout << "NIE" << endl;
      else cout << "TAK" << endl << ans << endl;
      g.clear();
    }
  }
  void main() {
    uint z; cin >> z;
    for (uint i(1); i <= z; ++i) test_case::main();
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 37404kb

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: -100
Dangerous Syscalls

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:


result: