QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#99026 | #5504. Flower Garden | KHIN | RE | 8ms | 37404kb | C++14 | 5.3kb | 2023-04-21 08:57:54 | 2023-04-21 08:57:56 |
Judging History
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...