QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#393078#3049. Vector Fieldcrsfaa#AC ✓159ms10620kbC++141.6kb2024-04-18 08:44:122024-04-18 08:44:14

Judging History

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

  • [2024-04-18 08:44:14]
  • 评测
  • 测评结果:AC
  • 用时:159ms
  • 内存:10620kb
  • [2024-04-18 08:44:12]
  • 提交

answer

#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
const int mxn=3005;
int x[mxn],y[mxn];
vector<int> e[mxn];
int cnt[mxn];
bool vis[mxn];
char v[mxn];
int dfs(int d)
{
//	cout<<d<<' '<<e[d].size()<<endl;
	vis[d]=1;
	while(cnt[d]<e[d].size()&&vis[e[d][cnt[d]]]) cnt[d]++;
	if(cnt[d]==e[d].size()) return 1;
	return dfs(e[d][cnt[d]])+1;
}
bool cmp1(int a,int b)
{
	return x[a]<x[b];
}
bool cmp2(int a,int b)
{
	return x[a]>x[b];
}
bool cmp3(int a,int b)
{
	return y[a]<y[b];
}
bool cmp4(int a,int b)
{
	return y[a]>y[b];
}
int main()
{
	int n=read(),i,j;
	for(i=1;i<=n;i++)
	{
		char s[5];
		y[i]=read(),x[i]=read();
		scanf("%s",s);
		v[i]=*s;
	}	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(v[i]=='v')
			{
				if(y[i]==y[j]&&x[j]>x[i])
					e[i].push_back(j);
			}
			if(v[i]=='^')
			{
				if(y[i]==y[j]&&x[j]<x[i])
					e[i].push_back(j);
			}
			if(v[i]=='>')
			{
				if(x[i]==x[j]&&y[j]>y[i])
					e[i].push_back(j);
			}
			if(v[i]=='<')
			{
				if(x[i]==x[j]&&y[j]<y[i])
					e[i].push_back(j);
			}
		}
		if(v[i]=='v') sort(e[i].begin(),e[i].end(),cmp1);
		if(v[i]=='^') sort(e[i].begin(),e[i].end(),cmp2);
		if(v[i]=='>') sort(e[i].begin(),e[i].end(),cmp3);
		if(v[i]=='<') sort(e[i].begin(),e[i].end(),cmp4);
	}
	int mx=0;
//	dfs(5);
	for(i=1;i<=n;i++)
		memset(vis,0,sizeof(vis)),memset(cnt,0,sizeof(cnt)),mx=max(mx,dfs(i));
	cout<<mx;
}

详细

Test #1:

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

input:

9
0 0 v
1 0 >
2 0 <
0 1 >
1 1 v
2 1 v
0 2 ^
1 2 ^
2 2 <

output:

9

result:

ok single line: '9'

Test #2:

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

input:

9
0 0 ^
1 0 ^
2 0 ^
0 1 <
1 1 ^
2 1 >
0 2 v
1 2 v
2 2 v

output:

2

result:

ok single line: '2'

Test #3:

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

input:

5
0 -1 >
-1 0 <
-1 1 ^
1 1 v
-2 2 ^

output:

2

result:

ok single line: '2'

Test #4:

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

input:

9
-1 1 ^
1 2 >
-2 2 ^
2 0 >
1 -2 >
0 2 >
0 0 <
-2 -2 v
-1 -2 v

output:

2

result:

ok single line: '2'

Test #5:

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

input:

7
-2 1 >
2 -1 v
1 2 v
1 1 ^
-1 1 v
-2 -2 >
-2 0 >

output:

2

result:

ok single line: '2'

Test #6:

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

input:

7
2 0 ^
-2 -2 ^
0 1 v
1 2 >
-1 1 ^
1 0 <
2 -1 <

output:

2

result:

ok single line: '2'

Test #7:

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

input:

8
1 -1 >
2 1 >
2 -1 v
-2 -1 >
2 0 ^
0 -2 ^
1 0 <
-2 0 v

output:

4

result:

ok single line: '4'

Test #8:

score: 0
Accepted
time: 3ms
memory: 3808kb

input:

1649
-56 133 v
186 53 >
-166 190 ^
-160 46 ^
-200 -122 v
145 -52 >
-51 -59 >
19 81 <
18 41 >
4 157 v
13 60 >
-55 -23 >
126 89 >
120 96 v
34 99 ^
-42 -24 >
-33 43 ^
-129 -62 >
66 9 <
53 -78 ^
104 -195 >
81 -177 <
134 99 v
-49 -185 >
97 -128 v
178 -147 v
-100 -42 ^
-77 40 <
109 -101 v
53 -84 v
-175 -1...

output:

26

result:

ok single line: '26'

Test #9:

score: 0
Accepted
time: 4ms
memory: 3892kb

input:

2104
-75 53 v
-68 125 >
70 -159 <
197 120 <
-8 193 v
-70 187 v
12 13 ^
-33 -124 v
114 -11 <
-98 -172 v
-145 -58 ^
169 -126 v
23 35 <
-168 190 >
51 -139 <
-147 181 ^
187 -77 >
-136 -183 >
-70 3 <
135 -38 v
132 -166 >
31 -118 v
170 145 v
83 39 ^
-39 -106 >
149 -158 ^
-99 28 >
199 -174 <
161 -188 <
58 ...

output:

26

result:

ok single line: '26'

Test #10:

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

input:

1583
-25 162 >
-127 -37 >
-45 -5 ^
151 -43 >
-78 116 v
146 -22 <
-152 172 >
140 -199 >
149 -49 ^
-38 -7 <
199 46 >
180 -2 ^
172 33 >
57 -193 <
-116 -185 >
134 6 v
34 0 <
-53 137 <
178 142 >
26 136 >
-90 -75 ^
69 -96 <
40 30 ^
166 -118 ^
195 37 v
-200 19 <
-72 -104 v
-121 -52 >
-143 199 v
10 138 v
10...

output:

18

result:

ok single line: '18'

Test #11:

score: 0
Accepted
time: 5ms
memory: 3984kb

input:

2282
-55 -31 ^
42 -97 ^
-180 177 v
-55 -87 v
-3 80 >
-11 182 >
-114 -198 v
100 175 <
87 -26 v
-102 39 ^
-130 88 ^
172 186 <
116 -79 ^
129 136 <
-157 -62 >
-143 153 ^
-36 28 v
-173 109 <
54 -109 ^
172 -57 ^
-109 64 <
-169 189 >
96 128 <
-170 -106 ^
47 64 v
34 -33 v
-20 33 <
192 -19 ^
-141 23 v
-92 95...

output:

29

result:

ok single line: '29'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3824kb

input:

2148
137 28 ^
-163 3 v
67 -176 v
-143 -94 >
-176 -99 >
-39 168 <
-97 120 <
72 -3 ^
-45 -14 <
-161 -77 <
-22 67 <
72 198 ^
67 -90 ^
-116 74 ^
-59 189 v
-150 -21 >
153 -146 <
-60 -56 <
-90 167 >
-128 174 ^
-173 -104 ^
35 -120 v
22 182 v
-131 134 v
-71 -179 >
-130 -64 <
-99 -141 >
-28 -168 >
66 -103 ^
...

output:

26

result:

ok single line: '26'

Test #13:

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

input:

9
756055265 109310155 v
-397828205 690307363 >
-285947139 -517659711 <
109114097 -517659711 ^
109114097 690307363 ^
756055265 -517659711 v
309866381 690307363 ^
756055265 -618705681 v
-285947139 -618705681 ^

output:

3

result:

ok single line: '3'

Test #14:

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

input:

6
321141521 -362997726 v
-186342646 -306948204 v
443436944 -306948204 v
-277760742 -615779940 <
-186342646 -615779940 >
-157131322 -362997726 v

output:

1

result:

ok single line: '1'

Test #15:

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

input:

6
958886539 -908906882 v
234250417 -671994996 v
958886539 -456995151 ^
192774675 -456995151 ^
958886539 -881251379 v
192774675 -908906882 v

output:

3

result:

ok single line: '3'

Test #16:

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

input:

10
-362600864 -995207706 ^
210886066 -995207706 <
210886066 -76786445 <
-61022755 270816884 >
-61022755 -76786445 >
-700203344 -794999484 ^
84573230 270816884 v
210886066 -794999484 <
-362600864 270816884 <
-61022755 823805139 >

output:

2

result:

ok single line: '2'

Test #17:

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

input:

7
452219819 946386942 >
-850796752 946386942 v
99237784 573200072 >
99237784 -811502033 <
99237784 946386942 v
890580838 -811502033 >
-836106429 573200072 >

output:

2

result:

ok single line: '2'

Test #18:

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

input:

9
963557176 401353650 ^
963557176 36055177 ^
189926017 124632049 v
-419550061 398133334 v
189926017 398133334 <
-733483210 36055177 v
963557176 124632049 ^
189926017 970155210 ^
-419550061 401353650 >

output:

7

result:

ok single line: '7'

Test #19:

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

input:

9
-414208444 -758737305 ^
738138366 -360720857 ^
759520343 -758737305 <
759520343 312946536 v
910144728 312946536 v
759520343 -360720857 v
910144728 -220351897 >
-657116712 312946536 v
910144728 -360720857 ^

output:

2

result:

ok single line: '2'

Test #20:

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

input:

6
680360677 -615845610 ^
228283842 -657406596 <
228283842 -989924458 v
-350124564 279370044 v
-255743301 -615845610 ^
-255743301 -657406596 >

output:

3

result:

ok single line: '3'

Test #21:

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

input:

7
363132285 -615084524 >
-362077693 -765313284 v
-362077693 -615084524 ^
167538717 -495961642 ^
492587739 -700482566 >
492587739 -495961642 >
176947979 -615084524 v

output:

2

result:

ok single line: '2'

Test #22:

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

input:

10
-425499630 342275432 >
-819062677 -282133062 >
-425499630 -282133062 >
739604232 -774022646 <
-362386403 342275432 <
-362386403 -774022646 v
-425499630 -965268116 <
-425499630 -774022646 <
457122182 -387198118 v
-362386403 -387198118 <

output:

3

result:

ok single line: '3'

Test #23:

score: 0
Accepted
time: 7ms
memory: 4000kb

input:

2688
-326052066 -213365685 <
-266158435 453580756 >
-222340587 -419108788 ^
776466171 193958257 v
456661076 676428669 v
-982186030 137293333 >
811624210 344376770 >
-904544613 -155127296 v
-584758261 -809473197 v
430417860 -146543101 >
815976051 -953026491 >
973979727 801463253 ^
4809453 509878349 >...

output:

43

result:

ok single line: '43'

Test #24:

score: 0
Accepted
time: 3ms
memory: 3848kb

input:

1638
995696293 -328077243 ^
745119087 -610644302 ^
892680226 -249569421 v
758615258 908931633 v
445891022 -134742493 v
-574814449 -791576929 ^
418513322 317546669 v
-746193489 276378856 v
-552210011 -525002289 ^
-927869496 -968053731 ^
-314334008 392830151 >
122483098 -484366345 >
433762545 -8232017...

output:

18

result:

ok single line: '18'

Test #25:

score: 0
Accepted
time: 3ms
memory: 3856kb

input:

1577
-809744633 -234037983 v
813650191 -157485215 ^
-837447098 679002963 ^
-404229005 729528284 >
288848075 96691118 <
-396136687 375860384 <
-860943968 549015655 >
-85525056 -556458592 >
-742925613 365687092 >
-757733878 513518076 ^
-235074168 932578781 <
-722185803 -501773083 >
-488125807 30704537...

output:

24

result:

ok single line: '24'

Test #26:

score: 0
Accepted
time: 4ms
memory: 3964kb

input:

1924
-52210434 -192432789 ^
549130324 346056179 <
881208393 -713795983 v
430260027 -987200820 ^
-256120842 354348295 <
-780849397 271322887 ^
-306499262 100673903 <
-908544127 -649573467 ^
-949305701 16450939 >
426538676 -759595066 >
184923292 496071925 ^
95649635 -694388577 ^
249455081 -312514156 >...

output:

25

result:

ok single line: '25'

Test #27:

score: 0
Accepted
time: 3ms
memory: 3932kb

input:

1680
372725559 -60527259 <
-339805729 621836810 >
130067783 -140295146 <
715742615 556017697 <
-550583900 239424220 v
624412964 610009601 <
-548285344 604461768 >
341416821 539672694 ^
-999830717 578315518 v
923253879 -91444622 ^
369948597 -460484153 ^
722273807 -683915416 ^
-587347889 445975798 ^
-...

output:

20

result:

ok single line: '20'

Test #28:

score: 0
Accepted
time: 5ms
memory: 3828kb

input:

2149
-893410833 595870911 >
-50607316 -370271060 <
423948214 -392383737 >
-867718018 867553649 ^
523045450 381826644 >
617746618 222073523 >
456626669 -774518982 >
550257322 -199776710 v
109799644 453331921 <
498109217 -833381128 ^
372858692 -497518451 <
-479691246 -736360388 >
-637725078 -736360388...

output:

22

result:

ok single line: '22'

Test #29:

score: 0
Accepted
time: 7ms
memory: 3996kb

input:

2763
183731753 704943022 >
-133812711 999484883 v
235877402 -992906320 ^
-878850239 396086990 <
62469537 740719820 >
244306754 -21799994 <
-425244557 837521885 ^
-116381106 -539290559 >
-945035198 -841590422 <
116714052 -140329922 >
258352423 693405804 ^
278662624 -149077016 v
-614122098 -521544325 ...

output:

28

result:

ok single line: '28'

Test #30:

score: 0
Accepted
time: 5ms
memory: 3924kb

input:

2374
799912995 768250 <
929865763 -347604155 <
-711172982 831309689 >
424069493 247566871 >
496149075 -131988168 ^
349724359 172506488 <
515629689 720375513 v
-7227757 81262054 v
-621697360 793415835 <
63167528 290443433 <
-988304241 -438861619 <
-590992361 -778891902 v
-138629116 865372542 >
-13862...

output:

54

result:

ok single line: '54'

Test #31:

score: 0
Accepted
time: 3ms
memory: 3860kb

input:

1691
622402952 126921962 >
-336036827 -88967880 v
640731378 -412987002 v
586434089 61466298 >
-592303006 372249232 >
45209842 136293222 >
24069602 984475090 v
980788258 -556423389 >
192604150 86274836 <
-131798103 85265063 v
228561939 -537567372 v
-865537678 147410743 ^
500175951 -186905489 ^
-92773...

output:

17

result:

ok single line: '17'

Test #32:

score: 0
Accepted
time: 7ms
memory: 3916kb

input:

2681
238582123 723868434 v
-245610328 320106274 ^
489164039 -718345193 ^
369594431 -742825841 >
157983586 -759824477 ^
-880914154 -511574633 >
-535031028 376290379 v
173541981 -742825841 <
552049675 915973098 ^
-240040366 79750904 ^
657763017 -353961670 <
-258930343 253628256 v
-93719637 -857905746 ...

output:

34

result:

ok single line: '34'

Test #33:

score: 0
Accepted
time: 121ms
memory: 10600kb

input:

2998
-399888308 714555763 ^
-399888308 -826683815 <
-977086208 -826683815 v
-977086208 714555763 >
-977086208 -117955722 v
-977086208 -87982878 v
-977086208 -153872180 v
-977086208 -108481406 v
-977086208 159363315 v
-977086208 -811427229 v
-977086208 -708821444 v
-977086208 234589566 v
-977086208 -...

output:

2996

result:

ok single line: '2996'

Test #34:

score: 0
Accepted
time: 99ms
memory: 10556kb

input:

3000
381552384 659078893 ^
381552384 -569156961 <
-655940705 -569156961 v
-655940705 659078893 >
-655940705 46507620 v
-655940705 54221709 v
-655940705 -57895207 v
-655940705 -463291232 v
-655940705 -325905467 v
-655940705 502104116 v
-655940705 -442948929 v
-655940705 318670281 v
-655940705 3753497...

output:

1887

result:

ok single line: '1887'

Test #35:

score: 0
Accepted
time: 121ms
memory: 10400kb

input:

2998
699189905 986087780 ^
699189905 354653 <
198158334 354653 v
198158334 986087780 >
198158334 687939789 v
198158334 461435145 v
198158334 812932566 v
198158334 12744077 v
198158334 711948460 v
198158334 848518286 v
198158334 501923899 v
198158334 129788604 v
198158334 240461981 v
198158334 947103...

output:

2996

result:

ok single line: '2996'

Test #36:

score: 0
Accepted
time: 158ms
memory: 10576kb

input:

2998
-172439524 14525191 ^
-172439524 -705286209 <
-868745959 -705286209 v
-868745959 14525191 >
-868745959 -559480754 v
-868745959 -576634588 v
-868745959 -199448243 v
-868745959 -104771174 v
-868745959 -484871578 v
-868745959 -321395395 v
-868745959 -432729957 v
-868745959 -324523047 v
-868745959 ...

output:

2998

result:

ok single line: '2998'

Test #37:

score: 0
Accepted
time: 159ms
memory: 10604kb

input:

2998
753971395 856723296 ^
753971395 -80235748 <
-166419752 -80235748 v
-166419752 856723296 >
-166419752 220678712 v
-166419752 454838704 v
-166419752 593507527 v
-166419752 638236849 v
-166419752 97554526 v
-166419752 429209693 v
-166419752 -35754487 v
-166419752 52344754 v
-166419752 127543262 v
...

output:

2998

result:

ok single line: '2998'

Test #38:

score: 0
Accepted
time: 95ms
memory: 10500kb

input:

3000
311576992 778653935 ^
311576992 -96818063 <
-280969870 -96818063 v
-280969870 778653935 >
-280969870 542167906 v
-280969870 180785951 v
-280969870 498258853 v
-280969870 342122422 v
-280969870 696082010 v
-280969870 230372118 v
-280969870 374957824 v
-280969870 707344766 v
-280969870 530165759 ...

output:

1997

result:

ok single line: '1997'

Test #39:

score: 0
Accepted
time: 155ms
memory: 10620kb

input:

2997
65140539 198385731 ^
65140539 -826771930 <
-902515057 -826771930 v
-902515057 198385731 >
-902515057 -376771609 v
-902515057 54484782 v
-902515057 -57601254 v
-902515057 -573186966 v
-902515057 -815783876 v
-902515057 -765111439 v
-902515057 -771079354 v
-902515057 -88145410 v
-902515057 -26081...

output:

2997

result:

ok single line: '2997'

Test #40:

score: 0
Accepted
time: 153ms
memory: 10484kb

input:

3000
-392465791 629000318 ^
-392465791 -90141632 <
-964555191 -90141632 v
-964555191 629000318 >
-964555191 200607877 v
-964555191 544625379 v
-964555191 147919641 v
-964555191 25553381 v
-964555191 337217305 v
-964555191 -76193872 v
-964555191 526001923 v
-964555191 336792184 v
-964555191 322787050...

output:

3000

result:

ok single line: '3000'

Test #41:

score: 0
Accepted
time: 116ms
memory: 10560kb

input:

2998
666475559 845463864 ^
666475559 -131298498 <
-933048661 -131298498 v
-933048661 845463864 >
-933048661 559122646 v
-933048661 651437844 v
-933048661 82732509 v
-933048661 132135478 v
-933048661 430368382 v
-933048661 188589758 v
-933048661 769407789 v
-933048661 217904594 v
-933048661 -57258310...

output:

2996

result:

ok single line: '2996'

Test #42:

score: 0
Accepted
time: 131ms
memory: 10520kb

input:

3000
813647065 126167709 ^
813647065 -520110988 <
-43308401 -520110988 v
-43308401 126167709 >
-43308401 -124107115 v
-43308401 -176561849 v
-43308401 -275476465 v
-43308401 84391969 v
-43308401 -360358869 v
-43308401 -9041468 v
-43308401 -13460344 v
-43308401 -128671148 v
-43308401 -433621217 v
-43...

output:

2984

result:

ok single line: '2984'