QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91725 | #5504. Flower Garden | Denisov | WA | 10148ms | 147852kb | C++20 | 6.2kb | 2023-03-29 14:43:35 | 2023-03-29 14:43:39 |
Judging History
answer
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
inline bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
inline bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL
const int max_n = -1, inf = 1000111222;
vector <pii> e;
int n;
vector <int> t, t1;
inline void upd (int v, int tl, int tr, int l, int r, int id, bool from) {
if (l > r) return;
if (tl == l && tr == r) {
if (from) {
e.pb({id, t1[v]});
}
else {
e.pb({t[v], id});
}
return;
}
int tm = (tl + tr) >> 1;
upd(v << 1, tl, tm, l, min(r, tm), id, from);
upd(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r, id, from);
}
int mx;
inline int build (int v, int tl, int tr) {
umax(mx, 3 * n + v + 1);
t[v] = 3 * n + v;
if (tl == tr) {
e.pb({tr, 3 * n + v});
return 3 * n + v;
}
int tm = (tl + tr) >> 1;
int L = build(v << 1, tl, tm);
int R = build(v << 1 | 1, tm + 1, tr);
e.pb({L, 3 * n + v});
e.pb({R, 3 * n + v});
return 3 * n + v;
}
inline int build1 (int v, int tl, int tr) {
t1[v] = mx++;
if (tl == tr) {
e.pb({t1[v], tr});
return t1[v];
}
int tm = (tl + tr) >> 1;
int L = build1(v << 1, tl, tm);
int R = build1(v << 1 | 1, tm + 1, tr);
e.pb({t1[v],L});
e.pb({t1[v],R});
return t1[v];
}
vector <vector <int> > g, gr;
vector <int> used, order, cl, w;
inline void dfs (int v) {
used[v] = 1;
for (int to : g[v]) {
if (!used[to]) {
dfs(to);
}
}
order.pb(v);
}
inline void dfs1 (int v, int c) {
used[v] = 2;
cl[v] = c;
w[c] += v < 3 * n;
for (int to : gr[v]) {
if (used[to] == 1) {
dfs1(to, c);
}
}
}
inline int go (int v) {
int ans = w[v];
for (int to : g[v]) {
ans += go(to);
}
return ans;
}
vector <int> ans;
inline void color (int v) {
ans[v] = 1;
for (int to : g[v]) {
color(to);
}
}
inline void color1 (int v) {
ans[v] = 0;
for (int to : gr[v]) {
color1(to);
}
}
inline void test_case () {
for (auto &i : g) i.clear();
for (auto &i : gr) i.clear();
g.clear();
ans.clear();
gr.clear();
t.clear();
t1.clear();
cl.clear();
w.clear();
used.clear();
order.clear();
e.clear();
mx = 0;
int q;
cin >> n >> q;
t.resize(3 * 4 * n);
t1.resize(3 * 4 * n);
build(1, 0, 3 * n - 1);
build1(1, 0, 3 * n - 1);
for (int i = 0, a, b, c, d; i < q; i++) {
cin >> a >> b >> c >> d;
--a, --b, --c, --d;
int cur = mx;
upd(1, 0, 3 * n - 1, c, d, cur, false);
upd(1, 0, 3 * n - 1, a, b, cur, true);
++mx;
}
//LOG("here");
int N = mx;
gr.resize(N);
g.resize(N);
for (auto &i : e) {
g[i.first].pb(i.second);
gr[i.second].pb(i.first);
}
used.resize(N);
for (int i = 0; i < N; i++) {
if (!used[i]) {
dfs(i);
}
}
reverse(all(order));
w.resize(N);
cl.resize(N);
int cmp = 0;
for (int i : order) {
if (used[i] == 1) {
dfs1(i, cmp);
++cmp;
}
}
for (int i = 0; i < cmp; i++) {
if (w[i] > 2 * n) {
cout << "NIE\n";
return;
}
}
for (auto &i : g) i.clear();
for (auto &i : gr) i.clear();
g.clear();
gr.clear();
gr.resize(cmp);
g.resize(cmp);
for (auto &i : e) {
if (cl[i.first] != cl[i.second]) {
g[cl[i.first]].pb(cl[i.second]);
gr[cl[i.second]].pb(cl[i.first]);
}
}
cout << "TAK\n";
ans.resize(cmp);
/// 1 - rose
/// 0 - violet
for (int i = 0; i < cmp; i++) {
if (w[i] > n) {
int res = go(i);
if (res <= 2 * n) {
color(i);
string answer(3 * n, 'F');
for (int j = 0; j < 3 * n; j++) {
if (ans[cl[j]]) {
answer[j] = 'R';
}
}
cout << answer << '\n';
return;
}
ans.assign(cmp, 1);
color1(i);
string answer(3 * n, 'R');
for (int j = 0; j < 3 * n; j++) {
if (!ans[cl[j]]) {
answer[j] = 'F';
}
}
cout << answer << '\n';
return;
}
}
order.clear();
used.clear();
used.resize(cmp);
for (int i = 0; i < cmp; i++) {
if (!used[i]) {
dfs(i);
}
}
int s = 0;
for (int v : order) {
s += w[v];
ans[v] = 1;
if (s >= n) {
assert(s <= 2 * n);
break;
}
}
string answer(3 * n, 'F');
for (int i = 0; i < 3 * n; i++) {
if (ans[cl[i]]) {
answer[i] = 'R';
}
}
cout << answer << '\n';
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
for (int test = 1; test <= t; test++) {
test_case();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3464kb
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 RFF NIE
result:
ok good!
Test #2:
score: 0
Accepted
time: 10148ms
memory: 147852kb
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: -100
Wrong Answer
time: 9570ms
memory: 123544kb
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:
wrong answer odpowiedz ma za malo/duzo roz!