Untitled

 avatar
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...