QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#588411#2401. Pizza Party!TenshiAC ✓92ms12052kbC++202.0kb2024-09-25 10:41:202024-09-25 11:41:58

Judging History

你现在查看的是最新测评结果

  • [2024-09-25 11:41:58]
  • 评测
  • 测评结果:AC
  • 用时:92ms
  • 内存:12052kb
  • [2024-09-25 10:41:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
 
#define x first
#define y second
using pii = pair<int, int>;
using ll = long long;
 
inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=6e5+5, M=N;

int Q;
map<string, int> mp;
int n;
vector<string> buf;

int get(string &s){
	if(mp.count(s)) return mp[s];
	return mp[s]=++n;
}

bool vis[N], ng[N];
queue<int> q;

struct Edge{
	int to, next;
	bool w;
}e[M];

int h[N], tot;

void add(int u, int v, bool w){
	e[tot].to=v, e[tot].w=w, e[tot].next=h[u], h[u]=tot++;
}

int din[N];

signed main(){
	memset(h, -1, sizeof h);
	cin>>Q;
	getchar();
	rep(i, 1, Q){
		string s;
		getline(cin, s);
		stringstream ssin(s);
		
		buf.clear();
		while(ssin>>s) buf.pb(s);
		
		if(buf.size()==1){
			vis[get(buf[0])]=true;
			q.push(get(buf[0]));
		}
		else{
			bool fl=false; 
			if(buf[2]=="and") fl=true;
			
			int v=get(buf.back());
			if(!fl){
				for(int i=1; i<(int)buf.size()-2; i+=2){
					auto &str=buf[i];
					int u=get(str);
					add(u, v, 0);
				}
			}
			else{
				int nv=++n;
				ng[nv]=true;
				for(int i=1; i<(int)buf.size()-2; i+=2){
					auto &str=buf[i];
					int u=get(str);
					add(u, nv, 1);
					din[nv]++;
				}
				add(nv, v, 0);
			}
		}
	}
	
	while(q.size()){
		int u=q.front(); q.pop();
		
		for(int i=h[u]; ~i; i=e[i].next){
			int go=e[i].to;
			if(!e[i].w){
				if(!vis[go]){
					vis[go]=true;
					q.push(go);
				}
			}
			else{
				if(--din[go]==0){
					if(!vis[go]){
						vis[go]=true;
						q.push(go);
					}
				}
			}
		}
	}
	
	int res=0;
	rep(i, 1, n) if(!ng[i]) res+=vis[i];
	cout<<res;
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 9760kb

input:

4
peppers
if spinach and olives then tomatoes
spinach
feta

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 0ms
memory: 11788kb

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: 0ms
memory: 9796kb

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: 1ms
memory: 7676kb

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: 1ms
memory: 7692kb

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: 1ms
memory: 11692kb

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: 92ms
memory: 11984kb

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: 92ms
memory: 12020kb

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: 2ms
memory: 12052kb

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: 1ms
memory: 7740kb

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: 0ms
memory: 7980kb

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: 4ms
memory: 9664kb

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: 1ms
memory: 7728kb

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: 1ms
memory: 9992kb

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: 14ms
memory: 7784kb

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: 14ms
memory: 9844kb

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: 13ms
memory: 9880kb

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: 13ms
memory: 9824kb

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: 11ms
memory: 9876kb

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: 15ms
memory: 10044kb

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: 41ms
memory: 9880kb

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: 37ms
memory: 11860kb

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'