QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#78080 | #5504. Flower Garden | jeffqi | WA | 5412ms | 494124kb | C++14 | 3.1kb | 2023-02-16 17:31:12 | 2023-02-16 17:31:15 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i = (a); i <= (b); ++i)
#define drep(i,a,b) for (int i = (a); i >= (b); --i)
#define LL long long
#define il inline
#define pii pair<int,int>
#define pll pair<LL,LL>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
il LL read() {
LL x = 0,y = 1; char ch = getchar(); while (!isdigit(ch)) {if (ch == '-') y = -y; ch = getchar();}
while (isdigit(ch)) {x = x*10+ch-'0'; ch = getchar();} return x*y;
}
namespace qiqi {
const int N = 5e6+5; int n,m,cnt,dfn[N],low[N],ord,num,stk[N],tp,vis[N],scc[N],siz[N]; char ch[N]; vector<int> e[N],g[2][N];
struct Seg {
#define ls (x<<1)
#define rs (ls|1)
int c,a[N<<2];
void build(int x,int l,int r) {
a[x] = ++cnt; if (l == r) {
return c ? e[l].pb(a[x]) : e[a[x]].pb(l);
}
int mid = l+((r-l)>>1); build(ls,l,mid); build(rs,mid+1,r);
if (c) {
e[a[ls]].pb(a[x]); e[a[rs]].pb(a[x]);
}
else {
e[a[x]].pb(a[ls]); e[a[x]].pb(a[rs]);
}
}
il void init(int n,int _c) {
c = _c; build(1,1,n);
}
void upd(int x,int l,int r,int pl,int pr,int k) {
if (pl <= l && r <= pr) {
return c ? e[a[x]].pb(k) : e[k].pb(a[x]);
}
int mid = l+((r-l)>>1);
if (pl <= mid) upd(ls,l,mid,pl,pr,k);
if (pr > mid) upd(rs,mid+1,r,pl,pr,k);
}
} seg[2];
il void f(int x,int p) {
scc[x] = p; vis[x] = 0;
if (x <= n) ++siz[p];
}
void tar(int u) {
dfn[u] = low[u] = ++ord;
stk[++tp] = u; vis[u] = 1;
for (auto v:e[u]) {
if (!dfn[v]) {
tar(v); low[u] = min(low[u],low[v]);
}
else if (vis[v]) {
low[u] = min(low[u],dfn[v]);
}
}
if (dfn[u] == low[u]) {
++num; do {
f(stk[tp],num);
} while (stk[tp--] != u);
}
}
il bool chk(int x) {
return x*3 >= n && x*3 <= n*2;
}
il void print() {
puts("TAK");
rep(i,1,n) printf("%c",ch[scc[i]]);
puts("");
}
il int sum(int u,int p) {
int res = siz[u];
for (auto v:g[p][u]) res += sum(v,p);
return res;
}
il void dfs(int u,int p,char c) {
ch[u] = c; for (auto v:g[p][u]) dfs(v,p,c);
}
void main() {
rep(i,1,cnt) {
dfn[i] = vis[i] = 0;
e[i].clear();
}
rep(i,1,num) {
siz[i] = 0;
rep(j,0,1) g[j][i].clear();
}
ord = num = 0;
cnt = n = 3*read(); m = read();
rep(i,0,1) seg[i].init(n,i);
rep(i,1,m) {
int a = read(),b = read(),c = read(),d = read();
++cnt; seg[1].upd(1,1,n,a,b,cnt); seg[0].upd(1,1,n,c,d,cnt);
}
rep(i,1,cnt) if (!dfn[i]) tar(i);
rep(u,1,cnt) for (auto v:e[u]) {
int x = scc[u],y = scc[v];
if (x != y) {
g[0][x].pb(y); g[1][y].pb(x);
}
}
rep(i,1,num) ch[i] = 'R';
rep(i,1,num) if (siz[i]*3 >= n) {
int x = sum(i,0);
if (chk(x)) {
dfs(i,0,'F'); return print();
}
x = sum(i,1);
if (chk(x)) {
rep(i,1,num) ch[i] = 'F';
dfs(i,1,'R'); return print();
}
puts("NIE"); return;
}
int x = 0; rep(i,1,num) {
x += siz[i]; ch[i] = 'F';
if (chk(x)) return print();
}
puts("NIE");
}
}
int main() {
int T = read(); while (T--) qiqi::main(); return 0;
}
详细
Test #1:
score: 100
Accepted
time: 44ms
memory: 366180kb
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: 3140ms
memory: 453060kb
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: 5412ms
memory: 494124kb
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:
NIE NIE NIE NIE NIE NIE NIE NIE NIE NIE
result:
wrong answer zla odpowiedz!