Untitled
unknown
plain_text
2 years ago
10 kB
5
Indexable
-------------------MAIN------------------------- #ifndef _CRT_SECURE_NO_WARNINGS #define _CRT_SECURE_NO_WARNINGS #endif #include <stdio.h> #define MAXL (11 + 1) #define CMD_INIT (100) #define CMD_ADD (200) #define CMD_DISTANCE (300) #define CMD_COUNT (400) extern void init(char mAncestor[], int mLastday); extern int add(char mName[], char mParent[], int mFirstday, int mLastday); extern int distance(char mName1[], char mName2[]); extern int count(int mDay); static bool run() { int Q; int ret = -1, ans; bool okay = false; scanf("%d", &Q); for (int q = 0; q < Q; ++q) { int cmd; char mName1[MAXL], mName2[MAXL]; int mDay1, mDay2; scanf("%d", &cmd); switch (cmd) { case CMD_INIT: scanf("%s %d", mName1, &mDay1); init(mName1, mDay1); okay = true; break; case CMD_ADD: scanf("%s %s %d %d", mName1, mName2, &mDay1, &mDay2); ret = add(mName1, mName2, mDay1, mDay2); scanf("%d", &ans); if (ret != ans) okay = false; break; case CMD_DISTANCE: scanf("%s %s", mName1, mName2); ret = distance(mName1, mName2); scanf("%d", &ans); if (ret != ans) okay = false; break; case CMD_COUNT: scanf("%d", &mDay1); ret = count(mDay1); scanf("%d", &ans); if (ret != ans) okay = false; break; default: okay = false; break; } } return okay; } int main() { setbuf(stdout, NULL); freopen("sample_input.txt", "r", stdin); int TC, MARK; scanf("%d %d", &TC, &MARK); for (int tc = 1; tc <= TC; ++tc) { int score = run() ? MARK : 0; printf("#%d %d\n", tc, score); } return 0; } -------------------USER-------------------------- #define MD 1000001 #define MB 12007 #define MX 1001 #define ML 45 #define ll long long #define f(i,x,n) for(register int i=x;i<n;i++) #define F __attribute((optimize("Ofast"))) struct Bact{ ll val; int pid, anc, lv, next; }P[MB]; int n, map[MB]; ll v; F void hashF(char *s){ v = 0; for(register int i=0;s[i];i++) v = (v<<5)|(s[i]&31); } F int getB(char *s){ hashF(s); int id = map[v%MB]; while(id&&P[id].val!=v) id = P[id].next; return id; } struct Group{ int b[MX], sum; }G[MX]; F void addB(char *s, int p, int b, int d){ hashF(s); P[n].val = v; if(p){ P[n].pid = p; P[p].lv%ML ? P[n].anc = P[p].anc : P[n].anc = p; P[n].lv = P[p].lv+1; } int h = v%MB; P[n].next = map[h]; map[h] = n++; int x = b/MX; int y = d/MX; if(x==y){ f(i,b%MX,d%MX+1) G[x].b[i]++; }else{ if(b%MX){ f(i,b%MX,MX) G[x].b[i]++; x++; } if((d+1)%MX) f(i,0,d%MX+1) G[y].b[i]++; else y++; f(i,x,y) G[i].sum++; } } F void init(char mAncestor[], int mDeathday){ f(i,0,MB) map[i] = 0; f(i,0,MX){ f(j,0,MX) G[i].b[j] = 0; G[i].sum = 0; } n = 1; addB(mAncestor,0,0,mDeathday); } F int add(char mName[], char mParent[], int mBirthday, int mDeathday){ addB(mName,getB(mParent),mBirthday,mDeathday); return P[n-1].lv; } F int distance(char mName1[], char mName2[]){ int id1 = getB(mName1); int id2 = getB(mName2); int dis = P[id1].lv + P[id2].lv; while(id1!=id2){ if(P[id1].anc==P[id2].anc){ while(id1!=id2){ if(P[id1].lv>P[id2].lv) id1 = P[id1].pid; else id2 = P[id2].pid; } }else P[id1].lv>P[id2].lv ? id1 = P[id1].anc : id2 = P[id2].anc; } return dis - 2*P[id1].lv; } F int count(int mDay){ int x = mDay/MX; return G[x].sum + G[x].b[mDay%MX]; } ----------------------INPUT-------------------------------- 25 100 11 100 ancestor 1000 200 childA ancestor 200 800 1 200 childB ancestor 300 1200 1 200 grandchildA childA 250 700 2 300 childB grandchildA 3 200 grandchildB childA 700 1500 2 200 grandchildC childB 800 2000 2 300 ancestor grandchildC 2 300 childB childB 0 400 900 4 400 700 5 37 100 yoqlvn 11026 200 yqk yoqlvn 806 120465 1 200 wpubk yoqlvn 679 573922 1 200 qlpyif wpubk 876 301191 2 200 pctr qlpyif 2053 392840 3 300 yqk pctr 4 400 159174 3 400 379563 2 400 523676 1 400 2051 4 200 iyc wpubk 1023 469300 2 300 yoqlvn qlpyif 2 400 537194 1 400 272003 4 300 pctr wpubk 2 300 yqk wpubk 2 300 qlpyif iyc 2 300 wpubk qlpyif 1 400 218324 4 300 yoqlvn iyc 2 300 qlpyif wpubk 1 300 wpubk wpubk 0 200 eigsfy qlpyif 1003 690675 3 200 ssor pctr 2777 687587 4 200 vgnmp yqk 1405 64205 2 300 vgnmp ssor 6 200 advy yqk 1573 257958 2 300 pctr iyc 3 400 0 1 300 advy wpubk 3 400 221430 7 300 qlpyif advy 4 200 zmqe iyc 1333 162554 3 300 vgnmp pctr 5 300 advy eigsfy 5 300 ssor yqk 5 400 440521 4 64 100 ahkkji 61930 200 bdjp ahkkji 65 217617 1 200 femso ahkkji 1444 115436 1 200 usgr femso 2637 93264 2 200 wzub femso 2889 211110 2 400 186675 2 200 mqeyb usgr 3381 942963 3 300 mqeyb mqeyb 0 200 chf bdjp 1191 912436 2 200 nkmzbq wzub 3425 861585 3 300 femso wzub 1 400 2637 5 300 chf chf 0 400 127998 5 400 178598 5 400 255089 3 300 ahkkji ahkkji 0 400 66227 7 300 chf wzub 4 300 femso usgr 1 200 kchsh chf 2089 980716 3 400 777735 4 300 usgr wzub 2 300 femso chf 3 400 647322 4 300 wzub ahkkji 2 300 kchsh mqeyb 6 300 femso usgr 1 300 femso chf 3 300 bdjp kchsh 2 400 571659 4 200 wmf bdjp 1445 596838 2 300 chf kchsh 1 400 2890 8 300 chf nkmzbq 5 300 bdjp wzub 3 300 nkmzbq wmf 5 400 446917 5 400 692929 4 300 bdjp nkmzbq 4 300 wzub chf 4 200 huswp kchsh 2486 462793 4 400 221803 6 400 1 1 400 245893 6 400 638300 4 300 kchsh mqeyb 6 400 914319 2 300 wzub wmf 4 400 3380 9 400 965166 1 300 femso kchsh 4 300 huswp bdjp 3 300 chf chf 0 300 wmf usgr 4 300 wzub mqeyb 3 400 852604 4 300 femso chf 3 300 bdjp mqeyb 4 300 kchsh huswp 1 300 bdjp wmf 1 300 nkmzbq femso 2 300 huswp mqeyb 7 300 nkmzbq bdjp 4 93 100 gywvta 44129 200 qlnng gywvta 355 751259 1 200 qgm qlnng 1763 29506 2 200 ugeq qgm 2064 160461 3 200 pcbxc qgm 2233 816484 3 400 447872 2 300 qlnng gywvta 1 300 qgm gywvta 2 300 qlnng gywvta 1 400 816484 1 300 qlnng qgm 1 400 686956 2 400 781136 1 400 159725 3 300 gywvta gywvta 0 400 354 1 300 ugeq gywvta 3 300 gywvta pcbxc 3 300 qlnng qgm 1 300 qgm qgm 0 300 qlnng qlnng 0 300 ugeq pcbxc 2 400 421297 2 300 pcbxc ugeq 2 300 pcbxc pcbxc 0 300 ugeq qlnng 2 400 4100 5 300 qlnng qlnng 0 300 ugeq gywvta 3 400 714867 2 300 ugeq qlnng 2 400 816484 1 400 254110 2 300 pcbxc qlnng 2 300 gywvta pcbxc 3 300 gywvta qlnng 1 300 qlnng qgm 1 200 qsmmo ugeq 3020 198965 4 400 382586 2 400 204783 2 400 2063 3 300 qgm pcbxc 1 400 267432 2 400 794456 1 300 pcbxc ugeq 2 300 ugeq qlnng 2 400 300402 2 300 ugeq ugeq 0 300 pcbxc qsmmo 3 200 jwiwr pcbxc 2956 996595 4 400 859921 1 300 jwiwr qgm 2 300 qgm gywvta 2 400 671379 3 300 qgm qlnng 1 400 317325 3 400 803849 2 300 gywvta pcbxc 3 400 353 1 200 qggawo ugeq 2431 905388 4 300 qsmmo qgm 2 300 qggawo gywvta 4 300 pcbxc jwiwr 1 200 pxly qggawo 3031 174845 5 400 347804 4 300 ugeq pxly 2 300 pcbxc qggawo 3 400 786646 3 300 gywvta gywvta 0 400 41773 8 300 gywvta pxly 5 200 nuc qggawo 3541 682299 5 300 jwiwr qlnng 3 200 ckmw pcbxc 2656 317254 4 300 qgm pcbxc 1 300 qsmmo pcbxc 3 400 3540 10 300 ugeq gywvta 3 300 pcbxc ugeq 2 300 qggawo qlnng 3 400 74131 9 200 kvpk nuc 3636 482496 6 300 gywvta jwiwr 4 200 esr kvpk 4089 808724 7 300 pcbxc nuc 4 400 404873 7 400 758959 4 300 qsmmo pxly 3 300 jwiwr ugeq 3 300 qggawo pcbxc 3 300 esr pxly 4 400 3033 10 300 qsmmo ugeq 1 123 100 ctduqk 33278 200 bqzhkq ctduqk 1087 861465 1 200 cwc ctduqk 420 146113 1 200 ahmz cwc 878 374147 2 200 hochtx ahmz 990 710465 3 400 538377 2 300 ctduqk ahmz 2 400 184918 3 300 hochtx bqzhkq 4 300 bqzhkq hochtx 4 200 xawel ahmz 914 607504 3 400 735597 1 300 hochtx ctduqk 3 400 861465 1 300 hochtx cwc 2 300 hochtx bqzhkq 4 300 bqzhkq hochtx 4 300 xawel ahmz 1 300 xawel cwc 2 300 cwc ctduqk 1 400 558730 3 400 639350 2 400 840826 1 200 lrzchz hochtx 996 760566 4 300 xawel bqzhkq 4 300 hochtx ahmz 1 400 421 2 300 cwc xawel 2 300 lrzchz hochtx 1 300 ahmz bqzhkq 3 400 25782 7 300 ctduqk lrzchz 4 300 xawel bqzhkq 4 400 751908 2 400 86580 6 200 poy lrzchz 1420 868804 5 400 172809 6 300 xawel lrzchz 3 300 cwc ahmz 1 300 bqzhkq poy 6 400 769928 2 300 ctduqk lrzchz 4 300 lrzchz poy 1 300 bqzhkq xawel 4 400 655115 4 300 xawel poy 4 400 319298 6 200 jlo poy 2420 616091 6 400 1085 6 300 hochtx lrzchz 1 400 686284 4 200 ernrev poy 2892 599185 6 300 hochtx poy 2 400 543019 7 300 cwc bqzhkq 2 200 wqyp jlo 3143 666787 7 300 ctduqk jlo 6 300 lrzchz ernrev 2 300 hochtx jlo 3 400 249123 9 300 ernrev poy 1 200 hvr wqyp 3161 602019 8 300 ahmz poy 3 300 ernrev cwc 5 400 805512 2 200 uagqex hvr 4167 99187 9 400 279494 10 400 143555 11 200 stg bqzhkq 1361 114432 2 400 677271 4 300 lrzchz bqzhkq 5 400 2892 11 400 344659 10 300 uagqex lrzchz 5 300 wqyp hvr 1 300 poy poy 0 300 lrzchz xawel 3 300 wqyp wqyp 0 400 155820 10 300 cwc cwc 0 300 ahmz stg 4 300 wqyp uagqex 2 300 hochtx hvr 5 400 399699 9 300 xawel ctduqk 3 300 xawel wqyp 6 400 998 6 300 cwc xawel 2 400 568234 9 200 hxt stg 1672 117528 3 200 nonjg bqzhkq 1929 63371 2 300 jlo stg 8 300 stg hvr 10 300 ernrev hxt 9 400 737702 3 400 657789 5 300 ahmz bqzhkq 3 300 uagqex lrzchz 5 300 wqyp stg 9 400 1089 7 400 432039 9 400 461805 9 300 wqyp ctduqk 7 400 538588 9 300 nonjg uagqex 11 400 1671 9 300 poy uagqex 4 300 stg ctduqk 2 300 hxt xawel 6 300 ctduqk stg 2 400 351778 10 300 hxt ernrev 9 300 ernrev ahmz 4 200 gez jlo 3860 494538 7 300 cwc ahmz 1 300 hvr uagqex 1 400 115239 13 400 700818 4 300 uagqex wqyp 2 300 hochtx bqzhkq 4 400 3162 15 300 stg jlo 8 300 ernrev gez 3
Editor is loading...