QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#19298 | #2401. Pizza Party! | Qingyu | AC ✓ | 102ms | 53424kb | C++20 | 1.6kb | 2022-01-29 00:29:14 | 2022-05-06 04:38:13 |
Judging History
answer
#include <bits/stdc++.h>
const int N = 1e6 + 50;
int sel[N], type[N], cond[N], count[N];
std::vector<int> args[N], tr[N];
std::map<std::string, int> map;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int n, tot = 0;
std::cin >> n;
auto get = [&](std::string s) {
if (!map.count(s))
map[s] = ++tot;
return map[s];
};
std::queue<int> que;
for (int i = 1; i <= n; ++i) {
std::string s;
std::cin >> s;
if (s != "if") {
int o = get(s);
sel[o] = 1;
que.emplace(o);
}
else {
std::string t, op;
std::cin >> t;
args[i].push_back(get(t));
while (1) {
std::cin >> op >> t;
if (op == "or") type[i] = 1;
else if (op == "and") type[i] = 2;
else {
cond[i] = get(t);
break;
}
args[i].push_back(get(t));
}
for (int j : args[i])
tr[j].push_back(i);
if (!type[i])
type[i] = 2;
//assert(type[i] == 1 || type[i] == 2);
}
}
while (!que.empty()) {
int o = que.front(); que.pop();
for (int t : tr[o]) {
assert(type[t] == 1 || type[t] == 2 || type[t] == -1);
if (type[t] == -1) continue;
if (type[t] == 1) { // or
type[t] = -1;
if (!sel[cond[t]]) {
sel[cond[t]] = 1;
que.emplace(cond[t]);
}
}
else {
++count[t];
if (count[t] == args[t].size()) {
type[t] = -1;
if (!sel[cond[t]]) {
sel[cond[t]] = 1;
que.emplace(cond[t]);
}
}
}
}
}
int ans = 0;
for (int i = 0; i <= tot; ++i)
if (sel[i])
++ans;
printf("%d\n", ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 13ms
memory: 50484kb
input:
4 peppers if spinach and olives then tomatoes spinach feta
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 20ms
memory: 50588kb
input:
5 pepperoni pineapple if pepperoni and sausage then mushroom ham if pineapple and ham then bacon
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 7ms
memory: 50592kb
input:
4 pepperoni sausage if pepperoni and sausage then mushrooms if mushrooms or peppers then cheese
output:
4
result:
ok single line: '4'
Test #4:
score: 0
Accepted
time: 8ms
memory: 50596kb
input:
5 a b if a and b then c if b and c then d if c and d then e
output:
5
result:
ok single line: '5'
Test #5:
score: 0
Accepted
time: 12ms
memory: 50680kb
input:
5 a b if a and b then c if b and c then d if d and e then f
output:
4
result:
ok single line: '4'
Test #6:
score: 0
Accepted
time: 8ms
memory: 50656kb
input:
3 if a then b if b then c if c then d
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 102ms
memory: 53424kb
input:
999 upvvrgtpje if upvvrgtpje then wgsjjrswxk if upvvrgtpje then ykrivldekw if upvvrgtpje and wgsjjrswxk then runoscfwls if upvvrgtpje and wgsjjrswxk then yfjsspckcj if upvvrgtpje and wgsjjrswxk and runoscfwls then qtibmdrmcr if upvvrgtpje and wgsjjrswxk and runoscfwls then rcwrvlwhbs if upvvrgtpje a...
output:
999
result:
ok single line: '999'
Test #8:
score: 0
Accepted
time: 100ms
memory: 53376kb
input:
999 bfrftvzqeq if bfrftvzqeq then twokijjtcs if bfrftvzqeq then azigteyfhr if bfrftvzqeq and twokijjtcs then gnkxblwxdg if bfrftvzqeq and twokijjtcs then xpgsvwmuvi if bfrftvzqeq and twokijjtcs and gnkxblwxdg then upgxsjhapz if bfrftvzqeq and twokijjtcs and gnkxblwxdg then nkonlwfqjw if bfrftvzqeq a...
output:
999
result:
ok single line: '999'
Test #9:
score: 0
Accepted
time: 4ms
memory: 50624kb
input:
100 etbl zmgw btwr azkw kzbe acdr bnvt fymr hijg jwql eilp zcwd benk fcli oxyq efbn xbiv ydej vgaj przk ipuw izpu zibj bsye agpz if etbl and ipuw and jwql and izpu and zibj and eilp and bnvt and fymr and vgaj and bsye and benk and laoy then qexa if oxyq and jwql and sypt and hnve and efbn and loyi a...
output:
35
result:
ok single line: '35'
Test #10:
score: 0
Accepted
time: 11ms
memory: 50648kb
input:
100 ctiw iqkw wceu jlxu alfu mxsn sjzb rzbd iefm sixd vmze gbup lxht hsqk biqg psbh sqhv nvil sbck nwax xqdj esav rlpj xvth mhwc if sqhv and dswr and ctiw and iqkw and nvil and gbup and sbck and hsqk and edlx and nwax and biqg and sjzb and fsaq and xvth and xqdj and rlpj and esav and psbh and rzbd a...
output:
36
result:
ok single line: '36'
Test #11:
score: 0
Accepted
time: 17ms
memory: 50872kb
input:
500 imea pkmc hqcl wjbh czma pogy ivmu cjzp bgnh iaxz brjm qgax geca biqu npbx nprh dczt vdcq khep dvwm dhon rgus ekzi cqut gsqz gked dnzk aqcl kdgc apsr mivu ekly wazr ngdv qslu cfdk exfh yptc wuzj rkjs tkry flex mrtd uzli mhku sult whnz ojnf rtpb nakq ykpg ymjf qlte aguy evcf cfjw wsdc heiz lfcw d...
output:
193
result:
ok single line: '193'
Test #12:
score: 0
Accepted
time: 10ms
memory: 50816kb
input:
500 aedp ivnw jpqo jrqz core jgdm nybu yplw dnlf rcot qodi recv flgw lvny tfnq jzgq mbvh oagd ayvn hsic vkzs bhnk scbk mxyr vinh okyn sgau adei umte tnej phxl sjqf fbtr ijhr ctbx hizc kltp cjty rqha gpwo azeq dbqa mjlz bmvw unfp cbnt iogl xftd jgfb bmsl ijdx iken ntck pdao menr ynrq uyja pxwy lbta x...
output:
196
result:
ok single line: '196'
Test #13:
score: 0
Accepted
time: 15ms
memory: 50548kb
input:
50 rlkt fabm jvpw nwos kigr hgdu esjk hopl pgrm kinl if rlkt and fabm and kigr and esjk and hopl and pgrm then jkzr if hgdu and fabm and hopl and kigr then yuda if rlkt and cjtl and jvpw and xzsf and hgdu and esjk and waoi and yveq and hopl and kinl then niqp if esjk and nwos and kinl then qgry if r...
output:
27
result:
ok single line: '27'
Test #14:
score: 0
Accepted
time: 13ms
memory: 50592kb
input:
50 qxak zyoq pzvj husm qtoc smhn vibl jxau uvek woja if qxak and mztr and zyoq and pzbl and smhn and vibl and dcvj and uvek and iqna then zcvm if hjki and qxak and husm and vibl then zild if yuxe and zyoq and qtoc and smhn and ovtr and gqli and tjkz then smif if qxak and pzvj and husm and vibl and w...
output:
24
result:
ok single line: '24'
Test #15:
score: 0
Accepted
time: 21ms
memory: 51248kb
input:
1000 ywah ljrt sabm szlo bnhl tsjp gjns eslo pvet hnda fqyx rzml vxcs wsfa hzsr sbeq ufxa mtad umoa vzui kyzw wmel dyxu xora dczw oacq pieh lvfz ynjm nbfe zmtl plgz qkwc uiyn uzdj cgxo dtor qylc bein rmwu hplc bfjm rkic jloi gmza qxap bpax niuv uhme mwpu vytx bgdk xiyz botg uobt dice yger raop tvcz ...
output:
275
result:
ok single line: '275'
Test #16:
score: 0
Accepted
time: 24ms
memory: 51220kb
input:
1000 dpfz aegi lubc lbge kvja wemn jldb gjeb ocqg zegw eprb jtwc hcdw uazd tdva zmeu prti royv ypnu fyuq enxu gosj oepg wyzt ktbm cpgj sztr xnbu xfjp pjhc dkpc qsir hrdc narj eflr frgn btig pkse barg ghov fqlu etlv ftkg rzjf czpk doau hnko tixe rnis ogpv xsiu kclq mwuv zlfg uenj zmlg unfj xeci esrn ...
output:
253
result:
ok single line: '253'
Test #17:
score: 0
Accepted
time: 21ms
memory: 51280kb
input:
1000 ixov upvf tzqi owfi rynu smnr cwxk vlja gcvx zupy sknq nqft lwui ifzs oswk yjec fwjx xkyr dhzo kozd kvnq umhs oaqw utif qfml jckq jkws ruma eqkl oxfe iopy redn pcyr hbkx mblg uozs xsar ljrn zigt cwgq bwdr owue nwzs wefa bxyz ocet rjnw ilev xrkp uhyp htzw dygu kvcg qnlw vank bnlw caqp vuft xrea ...
output:
322
result:
ok single line: '322'
Test #18:
score: 0
Accepted
time: 22ms
memory: 51152kb
input:
1000 elny jntl vbpx xedj hzro qfnk zsql fdhp lxjb plds hwmd rdji supn rpfy vamx namd hmqp svfg rjex yagm oxtm jrxc iljv hwsj gqti zhvd cpfo nkzv fxos voqt sdbt lumf exak hdue spqx iprb hqik xesp ujes rxfd zijs hvdq omck blva faie cosu dxey ksaw zrah uocq hdui ojue bday frzk ktja odtr osjw hjxp wfpu ...
output:
324
result:
ok single line: '324'
Test #19:
score: 0
Accepted
time: 32ms
memory: 51108kb
input:
1000 lpvo zfiq snpx dzsb fnit gkfu olxm alzv pkjc frez nkma bqnr snrd hzsm ewdy kwub liyg fzvd phme wqlg onmt duvs xekv fowp drcg grbm gzsc yuax kfth zuqb rjbu tapr gwix ushx rdvg pfey qirb zfik nhtl dvfw udjr etuk rjvp hdki xcno iofg zlia njto emin zsoq zdmu held lbio wxhe jdxf dqsn xysa uxen duyj ...
output:
146
result:
ok single line: '146'
Test #20:
score: 0
Accepted
time: 28ms
memory: 51216kb
input:
1000 jscb vhjb zwqv ackt dhqc ymsv jsvh iego nelt ydwo jdhv ewrs dqtc lvng jnmt kmta wrxn czjk dclz gcop sria hcbu xkqy gvjn khjd gecx weht ubpi dyjs ezjn smot fepj ntyu atkn wkgf opmv gehk rmsz sivf amlg ugna qivc nhfe kqwm forw rmez eswq knjp xqjy qhgm kvhc yatv cslt vtix lorc uike sdxg yghr tjfn ...
output:
150
result:
ok single line: '150'
Test #21:
score: 0
Accepted
time: 43ms
memory: 51972kb
input:
500 if xjzcpfifog and pxcwwwnjej and jvzrvpbuwp and jpdgfdmtfq and dchhcgygde and wplycpteqr and xjdjybstht and auluakkkpw and mouhhwhzcp and seglngligm and wnrvwfnzat and lxybuzhwhy and fbvcoqewvd and tyucbylspq and vjeyvjvwpz and vmywiolnjj and lufsolbohq and kijfgrdsvt and eleylssabm and uzxdaptf...
output:
500
result:
ok single line: '500'
Test #22:
score: 0
Accepted
time: 53ms
memory: 52020kb
input:
500 if ynmwyqaerq and ewuxlqzjmu and lynatfmyiw and xfhoqupbsw and sxwaiqwxcr and kwxeseomjv and dqarwcwsgh and xaymtlmnjl and obpuyatrix and vvsehvqulp and ssbenpknzm and lciboqwfbi and uiluceencf and ydxnhplddw and ibxxztpgzl and hsxrjkguiw and vanpakihob and vrxvwnmwhj and qjntrcnfzu and dgdhozsx...
output:
500
result:
ok single line: '500'