QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#5912 | #1301. 括号路径 | Qingyu | 100 ✓ | 317ms | 209040kb | C++17 | 1.9kb | 2021-02-06 18:38:27 | 2021-12-19 07:08:36 |
Judging History
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"