QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#5912#1301. 括号路径Qingyu100 ✓317ms209040kbC++171.9kb2021-02-06 18:38:272021-12-19 07:08:36

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2021-12-19 07:08:36]
  • 评测
  • 测评结果:100
  • 用时:317ms
  • 内存:209040kb
  • [2021-02-06 18:38:27]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<cctype>
using namespace std;
typedef long long ll;
int read()
{
	int x=0,ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x;
}
struct edge
{
	int v,w,x,nxt;
	edge(int v=0,int w=0,int x=0,int nxt=0):v(v),w(w),x(x),nxt(nxt){}
}e[10000005];
const int mod=4999977;
int h[5000005],t;
int gethash(int v,int w)
{
	return (v*128394ll+w)%mod;
}
int query(int v,int w)
{
	int u=gethash(v,w);
	for(int i=h[u];i;i=e[i].nxt)
	{
		if(e[i].v==v&&e[i].w==w)
			return e[i].x;
	}
	return -1;
}
void ins(int v,int w,int x)
{
	int u=gethash(v,w);
	for(int i=h[u];i;i=e[i].nxt)
		if(e[i].v==v&&e[i].w==w)
		{
			e[i].x=x;
			return;
		}
	e[++t].v=v;
	e[t].w=w;
	e[t].x=x;
	e[t].nxt=h[u];
	h[u]=t;
}
int n,m,k,f[300005],q[10000005][2],head,tail,sz[300005];
vector<edge> a[300005];
int getans(int x)
{
	if(x==f[x]) return x;
	return f[x]=getans(f[x]);
}
void link(int x,int y)
{
	x=getans(x),y=getans(y);
	if(x==y) return;
	if(a[x].size()>a[y].size()) swap(x,y);
	f[x]=y;
	sz[y]+=sz[x];
	int nw=a[x].size();
	for(int i=0;i<nw;i++)
	{
		edge nww=a[x][i];
		int qq=query(y,nww.w);
		if(qq!=-1)
		{
			q[++tail][0]=qq;
			q[tail][1]=nww.x;
		}
		else
		{
			ins(y,nww.w,nww.x);
			a[y].push_back(edge(0,nww.w,nww.x,0)); 
		}
	}
}
int main()
{
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++)
		f[i]=i,sz[i]=1;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		u=read(),v=read(),w=read();
		int qq=query(v,w);
	//	printf("qq=%d\n",qq);
		if(qq!=-1)
		{
			q[++tail][0]=qq;
			q[tail][1]=u;
		}
		else
		{
			ins(v,w,u);
			a[v].push_back(edge(0,w,u,0));
		}
	}
	while(head<tail)
	{
		head++;
		int u=q[head][0],v=q[head][1];
		link(u,v);
	}
	ll ans=0;
	for(int i=1;i<=n;i++)
		if(f[i]==i)
			ans=ans+1ll*sz[i]*(sz[i]-1)/2;
	printf("%lld\n",ans);
	return 0;
}

详细

Test #1:

score: 4
Accepted
time: 21ms
memory: 168260kb

input:

4 5 2
3 1 2
4 1 2
2 3 1
4 2 1
1 3 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 4
Accepted
time: 15ms
memory: 166816kb

input:

4 5 2
3 4 2
2 4 2
2 4 1
2 1 1
2 3 2

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 4
Accepted
time: 27ms
memory: 167276kb

input:

4 5 2
1 3 1
1 4 2
1 2 1
2 3 1
2 1 1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 4
Accepted
time: 7ms
memory: 167384kb

input:

4 5 2
2 4 1
3 4 1
1 2 2
4 2 2
3 1 1

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 4
Accepted
time: 16ms
memory: 167116kb

input:

8 10 2
4 8 2
5 2 2
8 7 1
4 1 1
5 7 2
5 7 2
7 8 1
2 7 2
6 5 1
8 7 2

output:

7

result:

ok 1 number(s): "7"

Test #6:

score: 4
Accepted
time: 8ms
memory: 167600kb

input:

8 10 2
2 6 1
7 8 2
3 6 2
3 7 1
8 7 1
8 7 1
7 2 1
1 5 2
2 8 2
7 8 1

output:

6

result:

ok 1 number(s): "6"

Test #7:

score: 4
Accepted
time: 24ms
memory: 167024kb

input:

8 10 2
6 7 2
2 6 1
2 7 2
1 3 1
6 2 2
2 8 2
8 6 2
1 2 2
6 8 1
5 7 2

output:

10

result:

ok 1 number(s): "10"

Test #8:

score: 4
Accepted
time: 21ms
memory: 167348kb

input:

8 10 2
3 8 2
3 7 1
6 8 1
6 1 2
3 4 1
8 5 1
4 7 1
7 2 2
1 6 1
6 3 1

output:

6

result:

ok 1 number(s): "6"

Test #9:

score: 4
Accepted
time: 16ms
memory: 176860kb

input:

3000 6000 1
1239 1740 1
2927 433 1
1102 329 1
2296 2920 1
2869 2230 1
266 466 1
2971 426 1
1268 2361 1
1777 749 1
648 2273 1
308 2354 1
759 2714 1
594 2679 1
1351 1623 1
1289 68 1
167 193 1
1014 1181 1
1297 2045 1
2496 807 1
2604 1723 1
1516 213 1
1953 1190 1
259 620 1
1425 775 1
1613 2083 1
1025 1307 1
888 1366 1
939 1987 1
95 2984 1
1498 2917 1
2368 798 1
1870 226 1
742 2262 1
2775 2994 1
2149 819 1
406 1667 1
839 1208 1
2914 90 1
1766 2470 1
3000 83 1
884 2339 1
1520 1870 1
2813 699 1
1332 90...

output:

3306307

result:

ok 1 number(s): "3306307"

Test #10:

score: 4
Accepted
time: 31ms
memory: 176900kb

input:

3000 6000 1
2950 2229 1
1031 1727 1
1170 2342 1
707 1346 1
635 1872 1
2884 1512 1
1931 1591 1
191 1928 1
2185 440 1
1628 1931 1
330 306 1
120 2782 1
146 1519 1
2766 112 1
2801 2180 1
2182 610 1
1540 1407 1
2220 1944 1
298 181 1
936 1971 1
560 2197 1
114 1750 1
994 2151 1
1142 1842 1
2533 1918 1
502 1712 1
2029 485 1
2915 2715 1
929 1533 1
1278 1631 1
3000 221 1
2296 1679 1
1274 1020 1
1677 290 1
1953 115 1
2611 527 1
2276 903 1
2841 1909 1
1702 906 1
1436 1876 1
208 2271 1
701 2022 1
789 509 1
1...

output:

3252528

result:

ok 1 number(s): "3252528"

Test #11:

score: 4
Accepted
time: 32ms
memory: 177244kb

input:

3000 6000 1
1435 2449 1
1950 1594 1
526 1195 1
1414 2093 1
433 2735 1
1883 2454 1
1238 2016 1
435 68 1
2155 1716 1
82 2587 1
1523 2603 1
1373 2260 1
1442 1013 1
661 2038 1
1973 1593 1
926 415 1
1754 968 1
2304 152 1
1499 435 1
2637 2270 1
278 2560 1
2136 2896 1
456 2375 1
2569 1575 1
1732 834 1
830 30 1
2391 2493 1
1529 2389 1
2368 2354 1
1072 1303 1
447 1586 1
1021 2557 1
2340 438 1
1702 1234 1
2333 2469 1
945 853 1
2460 1372 1
43 2029 1
2247 417 1
2614 843 1
415 769 1
2396 1616 1
1108 1532 1
3...

output:

3324331

result:

ok 1 number(s): "3324331"

Test #12:

score: 4
Accepted
time: 7ms
memory: 176652kb

input:

3000 6000 1
1673 1484 1
1006 1316 1
2889 171 1
609 463 1
2265 1207 1
1327 677 1
2874 1405 1
30 2254 1
1606 778 1
275 1762 1
970 2880 1
2099 147 1
59 985 1
982 1438 1
1938 770 1
538 936 1
1574 1465 1
2805 2022 1
69 336 1
789 920 1
35 1232 1
712 560 1
374 1203 1
1799 2721 1
2601 2122 1
428 1276 1
1184 389 1
2455 1374 1
1891 1698 1
1625 1938 1
602 1791 1
2995 2641 1
2708 2034 1
1030 1268 1
1240 1912 1
304 2123 1
1339 2784 1
2591 2415 1
324 1432 1
1920 1321 1
1445 288 1
2590 164 1
1849 2266 1
1390 9...

output:

3311453

result:

ok 1 number(s): "3311453"

Test #13:

score: 4
Accepted
time: 31ms
memory: 175088kb

input:

3000 2999 2
2913 837 2
2913 404 1
1533 837 1
1533 2487 1
2913 882 1
915 882 2
882 2402 2
1533 2657 2
2487 638 2
2657 75 2
638 472 2
638 908 1
996 882 1
1241 2402 2
591 1241 1
2394 2487 1
638 84 1
75 1147 1
170 2657 1
1147 310 1
300 472 2
908 411 1
2913 1011 1
84 1918 2
407 638 2
1533 2216 1
2216 1806 1
908 2545 1
2394 1389 1
84 2830 1
1598 1011 2
996 1858 1
1011 127 2
310 699 1
2778 170 2
84 1484 1
731 1858 2
2402 1004 2
2166 882 1
472 599 2
2590 599 1
818 1147 2
996 1089 1
996 1863 2
1755 2830 ...

output:

2972

result:

ok 1 number(s): "2972"

Test #14:

score: 4
Accepted
time: 16ms
memory: 174944kb

input:

3000 2999 2
2913 837 1
404 837 1
1533 837 2
2487 837 2
2913 882 2
1533 915 2
915 2402 2
2657 404 2
882 638 2
837 75 2
472 2913 2
908 2913 1
996 882 1
1241 638 1
638 591 2
882 2394 1
2657 84 1
1147 882 1
837 170 2
591 310 2
472 300 2
908 411 1
1011 1241 1
1918 310 1
407 404 2
915 2216 1
1806 2216 1
2216 2545 1
411 1389 2
2830 2487 1
1533 1598 2
2394 1858 1
127 84 1
699 2487 1
915 2778 2
1484 300 1
731 84 1
1484 1004 1
1858 2166 1
599 310 1
591 2590 2
75 818 1
1089 699 2
1806 1863 2
591 1755 1
196...

output:

2732

result:

ok 1 number(s): "2732"

Test #15:

score: 4
Accepted
time: 28ms
memory: 175424kb

input:

3000 2999 2
837 2913 1
2913 404 2
1533 2913 2
2487 2913 1
404 882 1
404 915 1
882 2402 1
2657 2487 1
2402 638 1
2487 75 2
915 472 1
915 908 1
404 996 2
1241 472 2
591 2657 1
882 2394 1
84 2402 1
1147 591 1
915 170 1
882 310 2
591 300 2
411 2657 2
2394 1011 1
411 1918 1
407 2657 1
2216 1011 1
1533 1806 2
591 2545 2
1389 638 2
1533 2830 1
591 1598 2
1858 2402 2
127 310 1
2394 699 1
2778 2657 2
2657 1484 1
731 2913 1
1004 2830 1
2166 407 1
599 915 1
1241 2590 1
407 818 1
1089 2487 1
1863 882 1
1755...

output:

3263

result:

ok 1 number(s): "3263"

Test #16:

score: 4
Accepted
time: 24ms
memory: 175392kb

input:

3000 2999 2
837 2913 2
2913 404 1
1533 2913 1
837 2487 1
404 882 1
915 404 2
2402 1533 1
2402 2657 2
2913 638 2
75 2913 1
75 472 2
908 2487 1
996 472 2
1241 404 2
591 75 2
2394 75 1
2402 84 1
1147 75 2
2402 170 2
310 908 2
170 300 2
75 411 2
915 1011 1
1918 75 2
411 407 2
591 2216 1
1011 1806 2
1147 2545 2
2394 1389 1
882 2830 2
1598 1806 1
300 1858 2
1806 127 1
404 699 1
2778 2545 2
1484 1858 1
75 731 1
1004 1241 2
2166 2487 2
837 599 2
2590 84 2
818 1484 2
599 1089 2
1858 1863 1
699 1755 1
196...

output:

2844

result:

ok 1 number(s): "2844"

Test #17:

score: 4
Accepted
time: 97ms
memory: 195796kb

input:

300000 299999 2
226607 242996 1
196602 242996 2
101456 242996 1
45720 226607 1
242996 106478 1
226607 74383 2
232752 101456 1
55049 232752 2
226607 192217 1
35296 74383 1
192217 286621 2
71800 101456 1
71800 287311 2
282373 196602 1
149651 282373 2
245286 106478 2
282373 291356 2
272972 74383 1
167161 286621 1
232752 159890 2
265407 286621 1
192217 39957 1
162275 242996 1
219246 35296 1
282373 4285 2
199267 74383 1
291356 94840 2
81692 94840 1
101456 272579 1
274300 35296 1
192217 207474 2
19926...

output:

1045151

result:

ok 1 number(s): "1045151"

Test #18:

score: 4
Accepted
time: 96ms
memory: 195892kb

input:

300000 299999 2
73200 174516 2
153341 73200 2
153341 71485 1
73200 292257 1
153341 185727 1
153341 278048 1
174516 77263 1
185727 213836 1
71485 147158 2
91541 153341 1
73200 205061 1
292257 238251 2
274719 73200 1
116566 91541 1
147158 220606 2
185727 220227 1
127555 238251 2
258405 220227 2
115319 127555 2
116566 39505 1
91541 131430 1
82824 220606 1
293260 73200 1
43736 205061 2
205061 233077 1
153341 282576 2
153341 110158 1
247310 220227 2
187163 77263 1
220227 77674 2
45632 278048 1
22228 ...

output:

1043517

result:

ok 1 number(s): "1043517"

Test #19:

score: 4
Accepted
time: 104ms
memory: 195936kb

input:

300000 299999 2
174516 73200 1
174516 153341 1
174516 71485 2
292257 153341 2
292257 185727 2
71485 278048 1
77263 292257 2
278048 213836 1
147158 73200 1
292257 91541 1
205061 91541 1
238251 213836 1
205061 274719 2
116566 292257 1
73200 220606 1
292257 220227 1
278048 127555 2
238251 258405 1
73200 115319 1
258405 39505 1
220606 131430 1
39505 82824 1
185727 293260 1
213836 43736 2
73200 233077 2
282576 292257 2
110158 274719 2
247310 147158 2
187163 77263 1
39505 77674 2
292257 45632 1
22228 ...

output:

1011407

result:

ok 1 number(s): "1011407"

Test #20:

score: 4
Accepted
time: 129ms
memory: 195992kb

input:

300000 299999 2
72111 268526 2
176640 72111 2
72111 25153 2
176640 183934 2
98063 183934 1
9751 72111 2
176640 258467 2
242290 25153 2
40118 25153 1
136412 176640 2
92133 72111 2
92331 176640 1
283286 40118 1
176640 83421 2
72111 244881 1
5787 258467 2
222867 242290 1
98063 55075 1
297294 55075 2
297294 13880 2
198320 83421 1
225926 55075 1
222867 82415 2
40118 250140 1
83421 117183 1
93973 92331 1
54115 9751 2
21003 54115 2
103809 25153 1
220081 117183 1
6013 198320 1
268526 208564 1
21003 2459...

output:

1260146

result:

ok 1 number(s): "1260146"

Test #21:

score: 4
Accepted
time: 280ms
memory: 207356kb

input:

300000 600000 50
14868 266444 24
107646 120858 29
145597 144649 18
5798 242942 44
130806 255066 2
137421 131698 42
232007 79600 13
230631 56780 42
116290 195485 15
277206 110652 41
17195 75692 16
63857 86868 22
151546 231440 25
245915 131598 12
95786 4146 12
95632 118765 17
242249 4096 21
129651 49148 14
284993 187298 33
74329 285068 41
102770 87063 19
161615 249094 26
234106 259652 50
44164 35149 4
195459 248787 15
161036 125707 13
77993 60600 42
131856 201437 36
167911 165466 29
56963 32954 4
...

output:

31435399684

result:

ok 1 number(s): "31435399684"

Test #22:

score: 4
Accepted
time: 303ms
memory: 207432kb

input:

300000 600000 50
248249 58279 41
5370 248476 46
109005 172385 10
281490 111909 13
121762 68485 29
192267 2000 1
89696 254672 1
44850 154565 45
285571 298168 34
190849 164952 40
233661 282335 34
90417 78056 38
35564 89518 44
99390 278646 4
12525 187253 6
248315 265937 5
115414 184345 9
164730 102826 21
243214 28082 10
82067 131992 16
210553 110966 22
298602 4883 26
99845 122999 26
201794 205844 30
297912 107846 33
136108 268832 12
37703 35750 38
269129 260760 4
38488 30027 7
289443 268457 13
6915...

output:

31423365278

result:

ok 1 number(s): "31423365278"

Test #23:

score: 4
Accepted
time: 269ms
memory: 209040kb

input:

300000 600000 50
46084 188175 39
273964 223141 31
126412 210480 17
124773 274098 15
71941 58914 21
240324 59030 45
125834 98862 18
296835 1381 18
286670 161485 27
102847 179956 16
116221 245612 23
225330 65587 13
32871 130137 20
262170 15577 30
136029 143696 1
91411 284158 43
53632 149813 33
20307 174194 28
35038 256818 10
53610 82667 5
19037 137854 37
140653 146822 7
179921 104227 44
277617 122502 35
201893 81050 25
250310 192638 38
193066 227797 21
95485 46048 33
85314 100194 47
141088 267319 ...

output:

31345949074

result:

ok 1 number(s): "31345949074"

Test #24:

score: 4
Accepted
time: 317ms
memory: 207432kb

input:

300000 600000 50
182738 52409 1
110533 49354 41
230616 98657 42
194919 172023 47
296699 113347 39
170721 295422 44
184728 186406 32
11971 177481 34
148953 146654 37
223873 178617 17
297433 150084 42
111395 141238 14
282185 93711 38
117822 141184 14
250030 279405 28
202347 206233 21
277610 297354 4
39377 277473 17
64475 278661 44
224593 286354 42
248577 163720 39
153579 199556 16
35539 275941 24
136140 212422 6
114327 214510 5
229748 219849 10
57230 20623 15
84623 196113 23
232563 128022 47
35745...

output:

31383517846

result:

ok 1 number(s): "31383517846"

Test #25:

score: 4
Accepted
time: 275ms
memory: 207472kb

input:

300000 600000 50
158973 244628 16
246492 227212 33
161971 229072 42
53166 119367 3
54422 223149 3
36662 244471 27
238142 292144 10
186871 208089 18
68132 238600 31
185264 208946 20
118206 7586 48
228884 91442 34
173431 234737 10
188679 293253 18
142549 217575 39
147624 17400 39
122387 64740 39
162954 248207 42
269063 61846 33
190720 98086 45
54914 96252 7
17373 76298 15
77571 171501 32
46703 96157 41
250024 183825 3
74587 124954 3
226128 283796 27
3738 114352 6
99799 246756 27
145757 134617 18
1...

output:

31434898175

result:

ok 1 number(s): "31434898175"