QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#497935	#8809. Telephone Plans	bachbeo2007	11	42ms	39092kb	C++23	2.5kb	2024-07-29 20:47:03	2024-07-29 20:47:09

Judging History

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

[2024-07-29 20:47:09]
评测

测评结果：11
用时：42ms
内存：39092kb

查看

[2024-07-29 20:47:03]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;
#define int long long

int sub,n,q;
int p[3*maxn],total,lst;

int vis[maxn],T;
int c[maxn],sz[2*maxn],cnt;
set<int> g[maxn];
set<int>::iterator ptr[maxn];

void add(int x,int y){
    if(sz[c[x]]>sz[c[y]]) swap(x,y);
    total+=sz[c[x]]*sz[c[y]];

    queue<int> q;
    q.push(x);vis[x]=++T;
    while(!q.empty()){
        int u=q.front();q.pop();
        c[u]=c[y];sz[c[y]]++;
        for(int v:g[u]) if(vis[v]!=T){q.push(v);vis[v]=T;}
    }
    g[x].insert(y);
    g[y].insert(x);
}

bool cmp(int x,int y){
    queue<int> qx,qy;
    qx.push(x);qy.push(y);
    vis[x]=vis[y]=++T;
    ptr[x]=g[x].begin();
    ptr[y]=g[y].begin();

    while(true){
        while(!qx.empty()){
            int u=qx.front();
            while(ptr[u]!=g[u].end() && vis[*ptr[u]]==T) ptr[u]++;
            if(ptr[u]==g[u].end()) qx.pop();
            else{
                int v=*ptr[u];
                ptr[v]=g[v].begin();
                vis[v]=T;qx.push(v);
            }
        }
        if(qx.empty()) return false;
        while(!qy.empty()){
            int u=qy.front();
            while(ptr[u]!=g[u].end() && vis[*ptr[u]]==T) ptr[u]++;
            if(ptr[u]==g[u].end()) qy.pop();
            else{
                int v=*ptr[u];
                ptr[v]=g[v].begin();
                vis[v]=T;qy.push(v);
            }
        }
        if(qy.empty()) return true;
    }
}

int del(int x,int y){
    g[x].erase(y);
    g[y].erase(x);
    if(cmp(x,y)) swap(x,y);

    cnt++;
    queue<int> q;
    q.push(x);vis[x]=++T;
    while(!q.empty()){
        int u=q.front();q.pop();
        c[u]=cnt;sz[cnt]++;
        for(int v:g[u]) if(vis[v]!=T){q.push(v);vis[v]=T;}
    }
    sz[c[y]]-=sz[cnt];
    int val=sz[cnt]*sz[c[y]];
    total-=val;
    return val;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> sub >> n >> q;
    cnt=n;
    for(int i=1;i<=n;i++) c[i]=i,sz[i]=1;
    for(int i=1;i<=q;i++){
        int op;cin >> op;
        if(op==1){
            int x,y;cin >> x >> y;
            if(sub) x^=lst,y^=lst;
            add(x,y);
        }
        else if(op==2){
            int x,y;cin >> x >> y;
            if(sub) x^=lst,y^=lst;
            p[i-1]+=del(x,y);
        }
        else{
            int t;cin >> t;
            if(sub) t^=lst;
            lst=total+p[i-1]-(i>t?p[i-t-1]:0);
            cout << lst << '\n';
        }
        p[i]=p[i-1];
    }
}

源文件, 语言: C++23

详细

Subtask #1:

score: 3

Accepted

Test #1:

score: 3

Accepted

time: 2ms

memory: 34376kb

input:

output:

result:

ok 147 lines

Test #2:

score: 3

Accepted

time: 4ms

memory: 36956kb

input:

output:

result:

ok 8 lines

Test #3:

score: 3

Accepted

time: 8ms

memory: 36816kb

input:

output:

result:

ok 92 lines

Test #4:

score: 3

Accepted

time: 0ms

memory: 36392kb

input:

output:

result:

ok 92 lines

Test #5:

score: 3

Accepted

time: 0ms

memory: 36540kb

input:

output:

result:

ok 92 lines

Test #6:

score: 3

Accepted

time: 0ms

memory: 35180kb

input:

output:

result:

ok 92 lines

Test #7:

score: 3

Accepted

time: 0ms

memory: 38024kb

input:

output:

result:

ok 92 lines

Test #8:

score: 3

Accepted

time: 0ms

memory: 35788kb

input:

output:

result:

ok 92 lines

Test #9:

score: 3

Accepted

time: 0ms

memory: 36700kb

input:

output:

result:

ok 92 lines

Test #10:

score: 3

Accepted

time: 0ms

memory: 36612kb

input:

output:

result:

ok 92 lines

Test #11:

score: 3

Accepted

time: 0ms

memory: 33360kb

input:

output:

result:

ok 92 lines

Test #12:

score: 3

Accepted

time: 0ms

memory: 35296kb

input:

output:

result:

ok 92 lines

Test #13:

score: 3

Accepted

time: 0ms

memory: 35964kb

input:

output:

result:

ok 92 lines

Test #14:

score: 3

Accepted

time: 4ms

memory: 35892kb

input:

output:

result:

ok 92 lines

Test #15:

score: 3

Accepted

time: 3ms

memory: 36168kb

input:

output:

result:

ok 92 lines

Test #16:

score: 3

Accepted

time: 0ms

memory: 35808kb

input:

output:

result:

ok 92 lines

Test #17:

score: 3

Accepted

time: 7ms

memory: 36808kb

input:

output:

result:

ok 92 lines

Test #18:

score: 3

Accepted

time: 3ms

memory: 35516kb

input:

output:

result:

ok 92 lines

Test #19:

score: 3

Accepted

time: 4ms

memory: 36104kb

input:

output:

result:

ok 92 lines

Test #20:

score: 3

Accepted

time: 4ms

memory: 36684kb

input:

output:

result:

ok 92 lines

Test #21:

score: 3

Accepted

time: 4ms

memory: 36584kb

input:

output:

result:

ok 94 lines

Test #22:

score: 3

Accepted

time: 8ms

memory: 36516kb

input:

output:

result:

ok 93 lines

Test #23:

score: 3

Accepted

time: 0ms

memory: 35192kb

input:

output:

result:

ok 92 lines

Test #24:

score: 3

Accepted

time: 0ms

memory: 35876kb

input:

output:

result:

ok 92 lines

Test #25:

score: 3

Accepted

time: 3ms

memory: 33112kb

input:

output:

result:

ok 92 lines

Test #26:

score: 3

Accepted

time: 3ms

memory: 36496kb

input:

output:

result:

ok 92 lines

Test #27:

score: 3

Accepted

time: 3ms

memory: 36768kb

input:

output:

result:

ok 139 lines

Test #28:

score: 3

Accepted

time: 0ms

memory: 36556kb

input:

output:

result:

ok 149 lines

Subtask #2:

score: 2

Accepted

Test #29:

score: 2

Accepted

time: 0ms

memory: 34668kb

input:

output:

result:

ok 147 lines

Test #30:

score: 2

Accepted

time: 4ms

memory: 33064kb

input:

output:

result:

ok 8 lines

Test #31:

score: 2

Accepted

time: 0ms

memory: 34608kb

input:

output:

result:

ok 92 lines

Test #32:

score: 2

Accepted

time: 4ms

memory: 34412kb

input:

output:

result:

ok 92 lines

Test #33:

score: 2

Accepted

time: 3ms

memory: 33804kb

input:

output:

result:

ok 92 lines

Test #34:

score: 2

Accepted

time: 4ms

memory: 33380kb

input:

output:

result:

ok 92 lines

Test #35:

score: 2

Accepted

time: 0ms

memory: 34768kb

input:

output:

result:

ok 92 lines

Test #36:

score: 2

Accepted

time: 0ms

memory: 35040kb

input:

output:

result:

ok 92 lines

Test #37:

score: 2

Accepted

time: 3ms

memory: 33556kb

input:

output:

result:

ok 92 lines

Test #38:

score: 2

Accepted

time: 0ms

memory: 33428kb

input:

output:

result:

ok 92 lines

Test #39:

score: 2

Accepted

time: 3ms

memory: 33528kb

input:

output:

result:

ok 92 lines

Test #40:

score: 2

Accepted

time: 4ms

memory: 34812kb

input:

1
30 150
1 23 18
3 1
3 0
1 22 12
3 5
3 0
1 16 20
3 4
3 1
3 14
1 17 5
3 1
3 6
1 5 29
3 14
1 4 29
1 29 23
3 5
3 14
3 12
1 22 14
3 8
1 40 54
1 54 42
1 38 41
3 41
1 79 83
3 79
3 84
3 82
1 67 79
3 73
3 83
1 86 95
3 122
3 117
1 112 100
3 106
3 109
3 105
1 107 101
3 120
3 175
3 135
1 155 150
3 138
1 140 13...

output:

result:

ok 92 lines

Test #41:

score: 2

Accepted

time: 3ms

memory: 33168kb

input:

output:

result:

ok 92 lines

Test #42:

score: 2

Accepted

time: 0ms

memory: 33664kb

input:

output:

result:

ok 92 lines

Test #43:

score: 2

Accepted

time: 0ms

memory: 34124kb

input:

output:

result:

ok 92 lines

Test #44:

score: 2

Accepted

time: 0ms

memory: 33464kb

input:

output:

result:

ok 92 lines

Test #45:

score: 2

Accepted

time: 4ms

memory: 35020kb

input:

output:

result:

ok 92 lines

Test #46:

score: 2

Accepted

time: 4ms

memory: 33380kb

input:

output:

result:

ok 92 lines

Test #47:

score: 2

Accepted

time: 3ms

memory: 34372kb

input:

output:

result:

ok 92 lines

Test #48:

score: 2

Accepted

time: 0ms

memory: 34536kb

input:

output:

result:

ok 92 lines

Test #49:

score: 2

Accepted

time: 0ms

memory: 32936kb

input:

output:

result:

ok 94 lines

Test #50:

score: 2

Accepted

time: 8ms

memory: 34024kb

input:

output:

result:

ok 93 lines

Test #51:

score: 2

Accepted

time: 3ms

memory: 34664kb

input:

output:

result:

ok 92 lines

Test #52:

score: 2

Accepted

time: 8ms

memory: 34468kb

input:

1
30 150
1 1 16
1 16 30
3 2
1 18 2
3 1
1 22 20
3 2
1 1 26
3 2
1 8 29
1 3 29
1 17 27
3 6
3 37
3 33
3 38
1 45 35
3 34
3 46
1 33 39
3 33
3 50
3 60
1 62 33
3 33
3 70
3 78
3 65
1 64 69
3 74
1 74 90
3 66
1 77 64
3 122
3 123
1 109 116
3 75
3 98
3 126
1 122 111
3 93
1 138 142
3 154
1 143 133
3 146
1 188 178...

output:

result:

ok 92 lines

Test #53:

score: 2

Accepted

time: 3ms

memory: 33416kb

input:

output:

result:

ok 92 lines

Test #54:

score: 2

Accepted

time: 0ms

memory: 34460kb

input:

output:

result:

ok 92 lines

Test #55:

score: 2

Accepted

time: 0ms

memory: 33672kb

input:

output:

result:

ok 139 lines

Test #56:

score: 2

Accepted

time: 4ms

memory: 34968kb

input:

output:

result:

ok 149 lines

Subtask #3:

score: 4

Accepted

Dependency #1:

100%

Accepted

Test #57:

score: 4

Accepted

time: 36ms

memory: 36884kb

input:

0
2000 6000
1 1455 291
1 291 432
1 1253 432
3 1
3 2
1 1458 1253
1 1458 689
3 7
1 597 689
1 597 1759
1 143 1759
1 1655 143
1 1655 878
1 878 817
1 817 871
3 15
3 6
1 871 1188
3 7
1 1188 815
1 815 1414
1 1414 1304
3 22
1 1257 1304
3 19
1 1257 493
1 1654 493
1 1654 327
1 327 240
1 240 1873
1 1873 1717
3...

output:

result:

ok 2002 lines

Test #58:

score: 4

Accepted

time: 32ms

memory: 36124kb

input:

0
2000 6000
1 203 393
1 1271 393
1 1271 1708
3 3
3 1
1 1708 311
1 458 311
1 458 271
1 835 271
3 4
1 37 835
3 8
3 5
1 37 1647
3 4
1 845 1647
1 1097 845
1 1835 1097
1 554 1835
1 1141 554
1 1141 1619
1 1619 1046
3 14
1 1046 1112
3 7
3 11
1 1112 13
3 8
3 7
1 246 13
3 2
1 246 1582
3 29
1 1582 183
3 23
1 ...

output:

result:

ok 2002 lines

Test #59:

score: 4

Accepted

time: 7ms

memory: 39092kb

input:

0
2000 6000
1 30 1101
1 327 480
1 535 666
1 718 1543
1 1945 1388
1 452 143
3 6
1 633 162
1 1555 1503
3 9
1 1790 508
3 1
1 1819 191
1 1599 1322
1 464 571
3 9
1 164 1069
1 149 1911
1 205 1889
1 84 1336
3 18
3 3
3 8
1 1931 1058
3 13
3 0
3 1
1 1099 294
1 1423 427
1 778 525
3 26
1 1268 540
1 1654 1749
1 ...

output:

result:

ok 2002 lines

Test #60:

score: 4

Accepted

time: 32ms

memory: 36792kb

input:

0
2000 6000
1 2000 1575
3 1
1 1575 1079
3 2
3 4
1 236 2000
3 4
3 2
1 837 2000
1 1765 1079
3 6
1 1079 1120
1 15 236
1 236 828
3 1
1 837 454
1 954 837
1 1471 1765
1 86 1765
3 10
1 2 1120
1 1204 1120
3 10
1 15 415
1 367 15
1 1499 828
3 13
1 1330 828
1 454 487
1 454 234
3 30
1 954 1528
1 954 596
1 943 1...

output:

result:

ok 2002 lines

Test #61:

score: 4

Accepted

time: 0ms

memory: 35840kb

input:

0
2000 6000
1 1740 751
3 0
1 369 751
3 3
1 1740 85
1 437 1740
3 2
1 385 369
3 1
1 1859 369
1 85 981
3 7
1 85 552
3 6
1 437 73
1 437 1741
3 11
1 385 1614
1 1887 385
1 1859 904
1 1859 756
3 21
1 1833 981
1 771 981
3 22
1 552 1974
1 552 1462
3 10
3 20
1 73 1680
3 22
3 26
1 1081 73
1 263 1741
1 1741 180...

output:

result:

ok 2002 lines

Test #62:

score: 4

Accepted

time: 3ms

memory: 34384kb

input:

0
2000 6000
3 0
1 774 1866
1 317 1083
3 1
3 2
1 553 1192
1 278 37
1 365 1201
3 5
1 1519 219
1 1669 386
1 208 205
1 530 571
1 1629 222
3 7
3 7
1 478 1627
1 16 1884
1 73 632
1 1841 212
3 20
1 1978 227
3 19
3 14
1 1673 582
1 750 982
1 1165 1853
1 1758 1148
1 1818 1286
1 1726 1935
3 4
3 31
1 1735 1316
1...

output:

result:

ok 2002 lines

Test #63:

score: 4

Accepted

time: 26ms

memory: 35332kb

input:

0
2000 6000
1 803 12
1 12 1370
3 0
1 12 516
3 4
1 12 672
1 12 1639
1 773 803
1 632 803
1 1354 803
3 2
1 803 1580
1 803 1691
1 729 1370
1 1370 1553
1 816 1370
1 1370 1364
3 7
3 11
1 1987 1370
3 19
1 641 516
1 588 516
3 11
1 1725 516
1 516 1554
1 516 1442
3 26
3 9
1 672 1766
3 13
1 672 188
3 13
3 15
1...

output:

result:

ok 2002 lines

Test #64:

score: 4

Accepted

time: 3ms

memory: 38548kb

input:

0
2000 6000
1 370 898
1 898 1052
1 244 898
1 898 1930
1 504 898
1 370 866
1 370 1266
3 5
1 1630 370
1 915 370
3 4
1 603 370
3 10
1 1866 1052
3 10
1 429 1052
3 1
1 1052 804
1 1052 325
1 35 1052
1 70 244
1 244 1796
3 19
1 244 238
1 244 414
1 1954 244
3 16
1 1930 874
3 22
1 1930 646
3 13
3 20
3 11
1 19...

output:

result:

ok 2002 lines

Test #65:

score: 4

Accepted

time: 3ms

memory: 34192kb

input:

0
2000 6000
3 0
1 367 962
1 26 1974
1 1570 1132
1 1050 1612
1 132 1746
1 1855 1903
1 371 1689
3 8
3 1
1 262 312
1 392 1030
1 869 1920
1 1101 23
3 14
3 10
3 11
1 176 652
3 9
3 3
3 2
1 1837 40
1 1249 849
1 1888 1820
3 10
3 24
3 16
1 1289 1454
1 1698 1295
1 49 1286
1 1954 176
3 31
3 30
1 1672 564
3 2
3...

output:

result:

ok 2002 lines

Test #66:

score: 4

Accepted

time: 31ms

memory: 35512kb

input:

0
2000 6000
1 1761 851
1 1761 543
1 1761 638
3 3
1 1761 615
3 4
3 1
1 1761 1629
3 3
1 1761 922
3 5
3 9
1 1495 1761
1 1321 1761
1 1761 1185
1 30 1761
3 9
1 426 1761
3 14
1 1761 941
1 295 1761
1 1761 905
1 1650 1761
3 4
1 659 1761
3 24
1 274 1761
1 46 1761
1 1761 1636
1 1348 1761
3 0
1 1761 1385
3 21
...

output:

result:

ok 2002 lines

Test #67:

score: 4

Accepted

time: 32ms

memory: 37004kb

input:

output:

result:

ok 2002 lines

Test #68:

score: 4

Accepted

time: 23ms

memory: 35876kb

input:

output:

result:

ok 2002 lines

Test #69:

score: 4

Accepted

time: 30ms

memory: 37304kb

input:

0
2000 6000
1 928 1128
1 1128 836
3 2
1 1743 1128
3 3
1 1128 309
1 1128 1361
1 1977 1128
1 95 1128
3 8
1 1128 93
1 1128 1804
1 1037 1128
3 0
1 1128 1282
1 1128 1887
1 1954 1128
3 6
1 1810 1128
1 1128 447
3 1
3 2
1 1128 12
1 1128 905
3 18
1 152 1128
1 1128 1576
1 396 1128
3 22
3 21
1 414 928
1 928 92...

output:

result:

ok 2002 lines

Test #70:

score: 4

Accepted

time: 5ms

memory: 35448kb

input:

0
2000 6000
1 1734 1244
1 55 1734
1 1734 1406
1 1734 1778
3 1
1 823 1734
3 6
1 1734 239
1 1951 1734
3 4
1 1795 1734
1 102 1734
3 7
3 7
1 1734 374
3 10
3 1
1 1239 1734
3 13
1 1103 1734
1 1734 373
1 1734 213
1 1734 1086
1 1734 1892
1 1969 1734
3 1
1 1734 1678
3 7
3 10
1 1857 1734
3 11
1 1911 1734
3 15...

output:

result:

ok 2002 lines

Test #71:

score: 4

Accepted

time: 7ms

memory: 34828kb

input:

0
2000 6000
3 0
1 1919 1490
1 1545 272
3 2
3 0
1 1699 1355
3 3
3 2
3 6
3 3
1 669 1969
3 2
3 6
1 1116 818
1 336 1584
1 1774 137
1 799 1168
3 14
1 645 729
1 837 876
3 4
1 1034 43
1 389 1869
1 966 872
1 2000 791
1 355 754
1 1065 1359
3 26
3 13
1 267 425
1 22 734
3 20
3 31
3 22
3 8
1 1770 1631
3 22
3 17...

output:

result:

ok 2002 lines

Test #72:

score: 4

Accepted

time: 32ms

memory: 35472kb

input:

0
1999 6000
1 1774 429
1 429 1860
3 2
1 1860 676
3 4
1 206 676
1 206 1533
3 2
3 7
1 1533 848
3 6
1 84 848
1 690 84
1 1757 690
1 593 1757
3 15
1 561 593
1 991 561
3 4
3 17
1 991 1411
3 11
1 1411 81
3 6
1 1673 81
3 10
1 888 1673
1 1651 888
3 20
1 1763 1651
3 26
1 1352 1763
1 259 1352
3 12
3 34
1 159 2...

output:

result:

ok 2004 lines

Test #73:

score: 4

Accepted

time: 6ms

memory: 37048kb

input:

0
1999 5999
1 732 101
1 101 377
3 2
3 2
1 1425 732
3 0
1 72 732
1 1697 377
3 3
3 7
1 1399 377
1 1425 1606
1 67 1425
3 4
1 72 1306
3 10
1 72 900
3 16
1 1613 1697
1 1697 1433
3 19
3 6
1 394 1399
3 10
1 1399 43
1 1821 1606
1 1606 1411
1 67 804
1 1317 67
3 10
3 15
1 823 1306
1 1306 654
1 1816 900
3 11
3...

output:

result:

ok 2003 lines

Test #74:

score: 4

Accepted

time: 42ms

memory: 36588kb

input:

0
2000 6000
1 1993 265
1 1767 265
1 265 712
1 1767 1266
3 0
3 1
1 517 1266
1 1496 517
1 517 1321
1 1767 435
1 435 527
1 834 517
3 7
1 517 485
1 517 1161
3 1
1 1161 552
1 485 1477
3 4
3 5
1 527 721
1 552 1912
1 1767 519
3 0
1 18 1767
3 22
1 435 244
1 449 1912
3 19
1 1912 922
3 7
1 1067 922
3 21
1 244...

output:

result:

ok 2002 lines

Test #75:

score: 4

Accepted

time: 5ms

memory: 35460kb

input:

0
2000 6000
1 559 1394
1 1394 1989
1 1843 1989
3 3
1 1843 301
1 301 1621
1 841 301
1 301 1178
1 841 1356
1 1178 1976
1 1669 841
3 3
1 1669 1562
3 7
1 1178 659
1 1976 1644
3 16
1 1501 659
3 16
3 19
1 1356 1197
1 1356 311
3 10
1 311 435
1 311 540
3 14
1 1989 1032
3 15
1 1356 172
1 1197 449
3 0
1 1987 ...

output:

result:

ok 2002 lines

Test #76:

score: 4

Accepted

time: 6ms

memory: 36708kb

input:

0
2000 6000
1 1023 824
3 0
3 2
1 889 21
1 1483 426
1 24 626
1 1393 1500
1 663 1284
1 858 1082
1 1254 272
1 557 517
1 1635 309
1 1486 1373
1 1980 978
1 1063 1459
1 2000 1225
1 608 116
1 785 1310
1 300 1362
3 5
3 14
3 19
3 18
3 18
1 805 1686
1 1760 523
1 816 1350
1 1691 591
1 376 892
1 482 729
3 0
3 9...

output:

result:

ok 2002 lines

Test #77:

score: 4

Accepted

time: 0ms

memory: 35680kb

input:

0
2000 6000
1 1836 1295
1 1270 1323
3 2
1 1207 790
3 1
3 4
1 1264 886
3 0
1 773 1387
1 216 1519
1 1566 1204
1 953 1308
3 9
1 215 1251
1 1233 162
3 1
1 1514 1111
1 445 530
1 475 1181
1 166 1969
3 3
3 14
3 19
3 5
3 1
1 1464 215
3 8
1 1908 1456
3 5
3 4
1 1046 980
1 789 1426
1 750 1508
3 8
3 14
3 22
1 1...

output:

result:

ok 2002 lines

Test #78:

score: 4

Accepted

time: 4ms

memory: 33348kb

input:

output:

result:

ok 6000 lines

Test #79:

score: 4

Accepted

time: 4ms

memory: 34196kb

input:

output:

result:

ok 6000 lines

Subtask #4:

score: 2

Accepted

Dependency #2:

100%

Accepted

Test #80:

score: 2

Accepted

time: 40ms

memory: 35008kb

input:

1
2000 6000
1 122 748
3 1
1 29 123
3 0
1 31 835
1 835 277
1 1395 277
3 7
1 1407 320
1 320 1690
1 1059 1690
3 10
1 113 1032
1 113 1880
1 1504 1880
1 1624 1504
1 1828 1624
3 38
1 251 1883
1 251 640
1 879 640
3 79
1 80 956
3 158
1 65 1297
1 1267 1297
1 1267 962
3 138
3 214
3 199
3 211
3 210
1 905 530
3...

output:

result:

ok 2002 lines

Test #81:

score: 2

Accepted

time: 37ms

memory: 35100kb

input:

1
2000 6000
1 1852 193
1 1852 428
1 1656 428
3 0
1 1662 1510
3 6
1 1514 1144
3 12
1 1259 1149
1 193 1259
3 5
1 820 210
1 1103 820
1 582 1103
1 1156 582
1 1156 429
1 429 818
1 707 818
1 707 940
3 27
1 134 968
1 338 134
1 338 1316
1 1333 1316
1 1665 1333
3 107
1 1781 1579
1 53 1781
3 206
1 1564 26
1 1...

output:

result:

ok 2002 lines

Test #82:

score: 2

Accepted

time: 4ms

memory: 34388kb

input:

1
2000 6000
3 0
3 0
1 538 1450
3 0
3 3
1 371 277
1 1292 996
1 846 423
1 327 166
1 708 1178
1 406 23
1 175 217
3 9
1 1293 1353
1 481 503
1 146 354
1 862 1857
1 1269 781
1 1676 193
1 220 1292
3 9
3 8
1 1126 907
1 759 26
1 1479 1644
1 220 1650
3 13
1 1011 1556
3 26
3 4
1 984 117
3 20
3 16
1 571 472
1 1...

output:

result:

ok 2002 lines

Test #83:

score: 2

Accepted

time: 33ms

memory: 35160kb

input:

1
2000 6000
1 237 1698
3 1
3 3
1 1078 236
1 1416 1699
3 3
1 978 1700
1 1073 1823
1 1052 1073
1 979 1423
1 1423 290
3 4
1 1599 1008
3 37
3 33
1 1579 1017
3 45
1 1838 150
1 1838 569
1 1069 1018
3 59
1 1089 997
1 910 204
3 78
1 1770 941
1 1881 348
3 115
3 143
1 1289 445
3 131
1 1712 821
3 164
1 1937 17...

output:

result:

ok 2002 lines

Test #84:

score: 2

Accepted

time: 4ms

memory: 34816kb

input:

1
2000 6000
1 1872 557
1 1872 197
1 557 627
3 2
1 555 654
1 195 1185
1 195 74
3 6
3 18
1 614 1466
1 497 614
3 30
1 1428 684
3 34
1 677 276
3 45
1 1876 1168
3 53
3 80
1 1412 1253
3 76
1 1078 2
1 2 715
3 75
1 842 1478
1 1842 1478
3 112
3 152
1 1351 364
1 364 193
1 590 1336
3 149
1 877 1294
1 197 391
1...

output:

result:

ok 2002 lines

Test #85:

score: 2

Accepted

time: 3ms

memory: 34568kb

input:

1
2000 6000
3 0
1 2000 63
1 1297 592
1 651 1184
1 949 476
3 0
1 1399 1451
1 627 1486
3 12
1 1633 760
1 728 1722
1 1612 677
3 10
1 1642 1890
3 11
3 5
1 1075 875
3 1
1 1457 815
1 695 511
1 1201 503
1 187 1233
1 607 1434
1 919 1957
1 809 6
1 897 77
3 1
1 1952 853
1 601 832
3 9
1 1206 1522
3 12
3 21
3 6...

output:

result:

ok 2002 lines

Test #86:

score: 2

Accepted

time: 31ms

memory: 34632kb

input:

1
2000 6000
1 1818 696
1 1818 1960
1 560 1818
1 1818 1900
1 1818 939
1 696 1760
3 4
3 23
1 1930 685
3 23
1 676 803
3 20
1 338 668
3 35
3 36
1 631 661
3 44
1 1951 1001
1 846 1951
3 51
3 93
1 547 2022
1 2022 690
1 270 2022
1 795 638
3 89
3 144
1 751 696
1 321 696
1 696 1300
3 137
1 412 654
1 2002 1110...

output:

result:

ok 2002 lines

Test #87:

score: 2

Accepted

time: 9ms

memory: 33884kb

input:

1
2000 6000
1 297 1312
3 1
1 386 296
1 296 746
1 457 296
1 296 1185
1 396 1313
1 1313 445
3 1
3 27
3 20
1 1340 884
3 31
1 1284 1201
1 1284 134
3 38
1 436 1686
3 63
1 449 149
3 72
1 461 830
3 64
3 92
1 551 472
1 1557 472
1 331 688
1 266 688
3 92
1 626 1079
1 626 1587
3 144
1 314 597
1 374 1696
1 1413...

output:

result:

ok 2002 lines

Test #88:

score: 2

Accepted

time: 3ms

memory: 34284kb

input:

1
2000 6000
3 0
3 1
3 1
1 591 1379
3 0
1 703 535
1 1018 863
3 3
3 2
1 1360 1900
1 179 887
1 475 1780
3 11
1 1863 138
3 13
1 169 50
1 1325 1423
1 1014 651
1 1047 936
1 1940 439
3 2
3 31
1 178 62
3 27
1 1799 302
1 1839 876
1 887 851
1 308 921
1 1965 551
3 0
1 262 1479
1 497 556
1 1681 281
1 293 1362
1...

output:

result:

ok 2002 lines

Test #89:

score: 2

Accepted

time: 31ms

memory: 33956kb

input:

1
2000 6000
1 1217 743
1 217 1217
1 40 1217
3 1
3 6
1 1223 1247
1 778 1223
1 1223 469
1 1094 1223
1 1778 1223
1 1550 1223
1 653 1223
1 1223 1072
3 0
1 1155 941
3 75
3 75
3 95
1 904 1167
3 67
1 1178 736
3 94
1 1192 1175
1 783 1192
3 99
1 1097 257
1 613 1097
3 143
1 145 1130
1 1130 936
1 906 1130
1 11...

output:

result:

ok 2002 lines

Test #90:

score: 2

Accepted

time: 32ms

memory: 33740kb

input:

output:

result:

ok 2002 lines

Test #91:

score: 2

Accepted

time: 23ms

memory: 33496kb

input:

output:

result:

ok 2002 lines

Test #92:

score: 2

Accepted

time: 29ms

memory: 33948kb

input:

1
2000 6000
1 76 1149
1 76 1087
3 2
3 1
1 79 1564
1 84 79
3 2
1 1147 70
3 8
1 1726 67
3 10
1 918 89
3 29
1 1069 80
1 80 723
3 31
1 97 891
1 97 971
1 1526 97
3 46
1 2 900
3 76
3 86
1 262 23
1 1099 23
1 1035 23
3 90
1 196 1422
1 196 1974
1 271 196
3 155
1 153 242
1 1219 1469
1 1219 1619
3 174
1 1152 9...

output:

result:

ok 2002 lines

Test #93:

score: 2

Accepted

time: 11ms

memory: 35144kb

input:

1
2000 6000
1 854 1405
1 1603 854
3 2
1 853 1067
3 7
1 1182 848
3 7
3 8
1 860 1605
3 10
1 857 356
1 563 857
1 857 1261
1 206 857
1 901 857
1 857 1609
1 857 607
1 857 1053
1 857 973
1 193 857
3 13
1 1705 814
1 407 814
3 111
3 153
1 975 2020
3 137
1 1357 1021
1 764 1021
1 1494 961
3 172
1 1434 1081
3 ...

output:

result:

ok 2002 lines

Test #94:

score: 2

Accepted

time: 13ms

memory: 33556kb

input:

1
2000 6000
3 0
3 0
1 406 304
3 1
1 1812 1549
1 1226 151
3 7
3 1
1 1953 1790
1 1304 1179
1 478 1304
1 307 1140
3 8
3 5
1 1267 1215
1 256 1336
3 10
1 1200 1762
3 12
1 1354 698
3 8
3 28
1 1662 702
1 16 120
1 1967 843
1 1770 1562
3 14
1 821 1379
1 1635 827
1 1555 1876
1 213 386
3 15
3 17
1 1101 646
1 1...

output:

result:

ok 2002 lines

Test #95:

score: 2

Accepted

time: 33ms

memory: 34092kb

input:

1
1999 6000
1 321 396
3 1
1 1753 397
1 1753 144
1 144 1241
1 1241 454
3 2
3 8
3 11
1 833 456
1 1232 833
1 429 1232
1 897 429
1 897 969
3 12
1 1143 1009
3 59
1 1026 1846
3 67
1 320 1850
1 320 831
1 1 831
3 72
1 399 55
1 399 678
3 105
1 170 583
3 140
1 1644 152
1 136 1644
1 136 533
3 160
1 601 270
3 2...

output:

result:

ok 2004 lines

Test #96:

score: 2

Accepted

time: 4ms

memory: 33284kb

input:

1
1999 5999
1 862 892
1 1004 892
3 1
3 0
1 861 848
3 2
1 256 856
1 1002 1101
3 2
1 995 961
1 1843 860
1 920 860
3 14
1 1255 290
1 919 290
3 39
3 39
1 1148 887
1 963 1148
1 1017 1692
3 62
3 75
1 917 903
1 1895 130
3 94
1 1860 2033
1 1007 39
1 1007 2045
3 120
1 2039 1128
1 1128 696
1 1278 792
1 252 79...

output:

result:

ok 2003 lines

Test #97:

score: 2

Accepted

time: 40ms

memory: 34664kb

input:

1
2000 6000
1 609 259
3 0
1 608 641
3 2
1 643 221
1 1127 221
1 256 613
3 0
3 10
1 409 617
1 209 1221
1 409 515
3 12
1 578 1266
1 1464 434
3 40
1 417 388
3 57
3 76
1 590 1180
3 72
1 1181 1168
3 76
1 1479 1660
3 86
1 474 1591
3 98
1 459 1858
1 1290 494
3 119
3 132
1 1955 445
3 137
1 1147 1144
1 151 17...

output:

result:

ok 2002 lines

Test #98:

score: 2

Accepted

time: 7ms

memory: 34296kb

input:

1
2000 6000
1 1088 841
3 1
3 3
1 840 764
1 1516 764
1 184 1516
3 5
3 12
1 698 759
1 759 310
1 179 1203
1 1203 175
1 175 1797
1 1174 1203
1 698 1810
1 1797 1178
1 794 1511
1 1843 175
3 8
1 1273 1077
3 96
1 1256 706
1 1192 1060
1 522 1192
1 302 1060
3 107
3 177
1 1070 1611
1 1058 1230
1 1611 646
3 171...

output:

result:

ok 2002 lines

Test #99:

score: 2

Accepted

time: 0ms

memory: 34688kb

input:

1
2000 6000
1 80 1939
1 121 1631
3 1
3 1
3 1
3 0
1 546 1609
1 1663 904
1 311 1360
1 410 1985
1 390 1767
3 10
1 368 721
1 1590 62
1 1176 515
1 95 1682
1 98 530
1 75 578
1 361 956
1 1051 244
1 2 71
3 1
1 1610 450
1 399 1298
3 0
1 1546 1882
1 487 1378
1 1039 1228
1 1513 1862
3 16
1 35 1139
3 21
1 1746 ...

output:

result:

ok 2002 lines

Test #100:

score: 2

Accepted

time: 6ms

memory: 35024kb

input:

1
2000 6000
3 0
1 838 577
1 953 369
3 0
1 1030 247
1 191 1389
1 1990 1730
1 355 199
1 1990 517
3 11
1 1789 216
1 391 319
1 1286 188
3 11
3 1
1 687 875
1 1093 1089
1 1062 1034
3 4
1 1558 824
1 1752 355
1 1759 1033
3 1
1 1145 101
3 7
1 1630 707
1 1191 781
3 24
3 4
1 1115 622
1 1406 1419
3 15
1 1353 97...

output:

result:

ok 2002 lines

Test #101:

score: 2

Accepted

time: 4ms

memory: 33344kb

input:

1
2000 6000
1 428 1670
3 1
1 661 429
1 1999 1671
3 0
1 1992 68
3 6
1 1481 72
3 14
1 266 667
3 5
3 22
1 272 151
1 1980 87
3 21
1 496 1933
3 42
3 33
1 175 559
1 111 611
3 43
1 295 0
3 71
1 122 299
3 66
1 429 533
1 318 703
3 90
3 99
3 100
1 398 187
1 250 517
1 1627 250
1 1195 76
3 107
3 187
1 475 1404
...

output:

result:

ok 5799 lines

Test #102:

score: 2

Accepted

time: 3ms

memory: 34188kb

input:

output:

result:

ok 5999 lines

Subtask #5:

score: 0

Time Limit Exceeded

Dependency #3:

100%

Accepted

Test #103:

score: 0

Time Limit Exceeded

input:

0
100000 300000
1 72195 62466
1 62466 62453
1 86364 62453
1 51654 86364
1 43288 51654
1 43288 16339
1 16339 787
1 787 92480
3 7
1 6912 92480
3 2
1 33178 6912
3 11
1 33178 67163
1 53048 67163
3 4
1 80720 53048
1 5642 80720
1 5642 84104
3 9
3 16
1 13753 84104
1 97278 13753
3 20
1 9284 97278
1 54758 92...

output:

result:

Subtask #6:

score: 0

Time Limit Exceeded

Dependency #4:

100%

Accepted

Test #126:

score: 0

Time Limit Exceeded

input:

1
100000 300000
1 99914 44637
1 54949 99914
1 30005 54949
1 30005 37908
1 82810 37908
3 3
1 82805 17647
1 81097 17647
3 14
1 81114 98590
3 20
1 98598 53663
1 8457 53663
1 12730 8457
3 36
1 21896 12764
1 21896 3379
1 54909 3379
3 76
3 97
1 54870 81162
1 81162 35892
1 35892 4762
3 126
1 4714 94599
1 9...

output: