QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#535599	#5113. Bridge	silver_muse	AC ✓	385ms	327500kb	C++20	884b	2024-08-28 10:52:59	2024-08-28 10:52:59

Judging History

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

[2024-08-28 10:52:59]
评测

测评结果：AC
用时：385ms
内存：327500kb

查看

[2024-08-28 10:52:59]
提交

answer

#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
#define ph push_back
using namespace std;

const int N=1e5+5,lim=800;
int n,m,q; 
int go[N][lim+5];
map<int,int>fa[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    for(int j=0;j<=lim;j++) go[i][j]=i;
    int B=(m+lim-1)/lim;
    while(q--)
    {
    	int op,x,y;
    	cin>>op;
    	if(op==1)
    	{
    		cin>>x>>y;
			if(y==m+1) continue;
    		y--;
    		int u=x,v=x+1;
    		fa[u][y]=v; fa[v][y]=u;
    		for(int i=y;i>=y/B*B;i--)
    		{
    			if(fa[u].find(i)!=fa[u].end()) u=fa[u][i];
    			if(fa[v].find(i)!=fa[v].end()) v=fa[v][i]; 
			}
    		swap(go[u][y/B],go[v][y/B]);
		}
		else
		{
			cin>>x;
			for(int i=0;i<=m/B;i++) x=go[x][i];
			cout<<x<<endl;
		}
	}
    return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 9432kb

input:

output:

result:

ok 10 numbers

Test #2:

score: 0

Accepted

time: 385ms

memory: 13880kb

input:

3 100000 99997
2 2
2 2
2 3
2 3
2 3
2 3
2 3
1 2 11047
1 1 98732
1 2 90045
1 1 43556
2 1
2 3
1 2 17242
1 1 17027
2 1
1 1 94195
2 1
2 2
2 1
2 3
1 1 34124
1 2 14354
1 2 673
1 2 39812
1 2 35520
1 2 16046
2 3
2 2
1 1 25410
2 3
2 1
2 3
2 2
1 2 55684
2 1
1 2 24811
1 2 92268
1 2 60268
2 2
1 1 89272
1 2 19232...

output:

result:

ok 60761 numbers

Test #3:

score: 0

Accepted

time: 27ms

memory: 322848kb

input:

100000 5 20
1 40277 1
2 55431
2 22404
2 29137
2 10206
2 72758
2 92880
1 96104 2
2 12641
1 99618 2
2 88481
1 76531 3
1 91957 5
1 23999 2
2 35922
1 69730 5
1 16353 2
1 90312 1
1 75264 5
2 77283

output:

result:

ok 10 numbers

Test #4:

score: 0

Accepted

time: 2ms

memory: 8336kb

input:

output:

result:

ok 16 numbers

Test #5:

score: 0

Accepted

time: 227ms

memory: 14856kb

input:

200 100000 99995
1 180 45150
2 137
1 97 78979
1 14 74747
1 151 41036
1 178 88736
1 26 50618
1 132 72623
1 95 37475
2 184
1 31 44675
1 183 14874
1 66 14597
2 191
2 102
1 27 61558
1 36 39304
2 119
2 185
1 156 50000
2 200
2 152
1 17 51778
1 39 39403
2 168
1 50 67213
1 92 56771
2 28
2 196
1 99 29006
2 4...

output:

result:

ok 50281 numbers

Test #6:

score: 0

Accepted

time: 43ms

memory: 10564kb

input:

200 100 100000
1 192 88
1 13 2
2 131
1 80 44
1 11 74
1 159 89
1 29 91
1 81 62
1 159 21
1 37 34
2 169
2 163
1 164 50
1 104 45
1 81 46
1 176 73
1 68 59
2 117
2 152
2 189
1 125 4
2 45
1 120 59
2 30
2 113
1 74 15
1 147 71
1 31 47
2 179
2 118
2 34
2 61
1 41 32
2 153
1 186 28
2 113
2 55
2 24
2 92
2 72
2 8...

output:

result:

ok 91618 numbers

Test #7:

score: 0

Accepted

time: 1ms

memory: 9612kb

input:

output:

result:

ok 11 numbers

Test #8:

score: 0

Accepted

time: 220ms

memory: 14344kb

input:

200 100000 99995
1 1 29447
2 147
2 132
2 90
1 140 58754
2 74
2 51
2 113
1 177 51453
1 160 35609
2 47
1 88 93756
2 17
2 180
1 9 95689
2 196
1 59 45390
2 90
1 156 83976
2 17
1 66 13781
1 68 82550
2 174
2 14
1 24 41452
1 29 39524
2 2
1 190 55163
1 27 80396
1 102 20535
2 112
2 66
1 69 84633
1 95 51235
1...

output:

result:

ok 50221 numbers

Test #9:

score: 0

Accepted

time: 37ms

memory: 9968kb

input:

3 100 99997
1 1 47
2 2
2 1
1 1 46
1 1 9
2 1
1 1 98
2 1
1 2 93
1 2 71
1 2 67
2 2
1 1 43
2 1
2 2
2 2
1 1 85
1 2 86
1 2 97
1 1 84
2 3
2 1
2 3
1 1 23
2 3
1 1 13
1 2 34
2 3
2 3
2 3
1 2 94
2 1
1 2 31
2 3
2 1
2 2
2 3
2 3
2 3
1 1 83
2 1
2 3
1 2 77
2 3
2 1
2 3
1 2 89
2 3
2 3
1 1 74
2 3
2 2
2 2
2 1
1 1 78
2 1...

output:

result:

ok 99897 numbers

Test #10:

score: 0

Accepted

time: 34ms

memory: 10280kb

input:

10 100 99996
2 2
2 1
2 5
1 8 23
1 5 44
1 6 86
1 3 38
1 5 65
1 8 87
1 6 9
1 6 62
2 4
2 10
2 6
2 2
1 4 14
1 4 54
1 2 7
2 9
1 1 41
2 8
1 1 52
2 8
1 6 63
2 3
1 2 27
2 1
1 6 99
2 5
1 8 16
1 1 16
1 4 35
2 1
2 4
1 4 25
2 2
1 2 66
2 10
1 7 56
2 5
1 2 70
1 8 32
2 2
1 6 71
2 9
1 6 33
1 8 74
1 6 31
1 7 24
2 10...

output:

result:

ok 99577 numbers

Test #11:

score: 0

Accepted

time: 30ms

memory: 9864kb

input:

10 100 100000
2 6
2 4
2 8
1 5 70
2 4
1 3 55
1 7 89
1 1 57
1 9 40
1 3 83
2 7
2 9
1 5 26
2 7
1 1 99
2 8
1 1 13
2 8
1 3 86
1 6 12
1 5 11
1 9 98
2 2
1 1 63
1 5 67
1 5 66
1 8 58
2 4
1 9 71
1 1 71
1 5 89
1 1 17
2 3
2 10
1 2 59
2 5
2 2
2 5
1 6 8
1 1 45
1 3 69
1 5 63
2 5
1 5 35
1 2 19
1 4 8
2 1
2 1
2 10
1 2...

output:

result:

ok 99580 numbers

Test #12:

score: 0

Accepted

time: 2ms

memory: 9708kb

input:

output:

result:

ok 8 numbers

Test #13:

score: 0

Accepted

time: 0ms

memory: 9940kb

input:

200 100000 20
2 67
2 2
2 183
1 113 37023
2 191
1 138 85049
2 118
1 139 45917
2 77
2 22
1 163 58926
2 105
2 47
1 154 52742
2 193
1 7 38889
2 196
2 101
2 55
1 37 36657

output:

result:

ok 13 numbers

Test #14:

score: 0

Accepted

time: 380ms

memory: 13620kb

input:

3 100000 100000
1 2 27703
2 1
1 1 4733
2 3
1 1 35779
2 3
1 2 75051
1 1 55567
1 2 67461
2 2
2 3
2 2
1 2 40504
2 2
1 2 66898
2 2
2 2
2 3
2 2
1 1 49407
1 1 40531
2 2
1 1 16364
1 1 20583
2 1
1 2 15074
2 3
1 2 52463
1 2 68707
2 3
1 1 2943
1 1 49490
1 1 21186
2 2
1 2 60207
2 3
1 1 69753
2 2
1 2 55020
1 2 ...

output:

result:

ok 60629 numbers

Test #15:

score: 0

Accepted

time: 224ms

memory: 15592kb

input:

200 100000 99996
1 9 50789
2 13
2 119
2 140
2 17
2 152
2 55
1 13 78327
1 86 75223
1 124 45493
1 61 18265
2 27
1 83 46963
2 44
2 2
1 24 66690
1 60 83558
2 190
1 17 74439
1 46 33383
1 33 865
1 65 31179
1 126 66418
1 24 87240
1 157 70780
1 39 64647
2 74
2 112
1 34 94471
1 118 59390
2 122
2 133
2 159
1 ...

output:

result:

ok 50119 numbers

Test #16:

score: 0

Accepted

time: 71ms

memory: 327484kb

input:

100000 100 99997
2 83146
1 92304 70
2 1316
2 67332
1 3999 7
1 87638 98
2 46517
2 9036
2 72931
1 99147 75
1 81076 94
2 35556
1 38226 77
1 70606 61
1 97514 72
2 59772
1 51823 100
1 34436 19
1 2566 38
2 35420
1 52972 14
1 59064 59
1 61862 80
1 23386 91
1 20343 59
2 40701
2 64037
2 92058
2 58963
2 30254...

output:

result:

ok 50227 numbers

Test #17:

score: 0

Accepted

time: 11ms

memory: 9808kb

input:

10 5 100000
1 9 3
1 1 2
1 9 2
2 7
1 8 4
2 3
2 6
1 4 2
2 4
2 5
2 10
2 2
2 8
2 10
2 10
2 8
2 8
2 6
1 5 3
2 3
2 5
1 6 2
2 3
2 5
2 4
1 5 1
1 3 4
2 10
2 3
2 2
1 1 3
1 7 3
1 1 1
2 5
1 4 5
2 4
2 2
1 2 5
2 9
2 5
2 5
2 9
2 3
2 9
2 4
2 8
2 9
2 7
2 8
2 2
2 4
2 8
2 3
2 5
2 8
2 2
2 6
2 2
1 6 4
2 7
2 10
2 7
1 8 1...

output:

result:

ok 99979 numbers

Test #18:

score: 0

Accepted

time: 11ms

memory: 9508kb

input:

output:

result:

ok 99975 numbers

Test #19:

score: 0

Accepted

time: 0ms

memory: 8928kb

input:

output:

result:

ok 13 numbers

Test #20:

score: 0

Accepted

time: 39ms

memory: 9900kb

input:

10 100 99997
1 3 38
2 9
2 9
1 7 44
2 3
2 9
1 3 29
2 7
2 2
2 9
2 3
1 8 58
1 7 19
2 6
2 4
2 8
1 7 71
2 5
2 2
2 6
2 5
2 2
1 4 43
1 5 11
1 4 2
2 5
1 8 50
2 3
1 8 70
2 6
1 4 99
1 4 80
2 3
1 8 74
1 7 77
2 2
1 4 60
1 4 68
2 1
1 6 34
1 5 3
1 7 79
1 5 24
1 2 84
1 9 71
2 8
1 8 27
2 7
1 3 3
1 5 21
2 3
2 5
2 8
...

output:

result:

ok 99581 numbers

Test #21:

score: 0

Accepted

time: 10ms

memory: 9036kb

input:

output:

result:

ok 99990 numbers

Test #22:

score: 0

Accepted

time: 0ms

memory: 8716kb

input:

3 100000 20
1 2 36763
1 2 3289
2 1
1 1 29434
2 2
2 1
1 2 51062
1 1 26892
2 2
1 1 30602
1 1 94867
1 1 23031
2 3
2 3
2 2
2 3
2 2
1 1 28678
1 2 84132
2 3

output:

result:

ok 10 numbers

Test #23:

score: 0

Accepted

time: 34ms

memory: 9868kb

input:

10 100 99997
2 4
1 1 72
1 7 26
1 7 43
2 8
1 5 44
2 7
2 9
2 8
1 4 86
1 8 10
1 3 96
1 5 97
1 6 69
1 2 91
2 5
2 6
2 5
1 6 98
1 2 40
1 4 17
1 9 95
2 5
2 8
2 7
1 8 86
1 4 25
1 6 94
1 8 79
2 1
1 9 74
1 1 63
1 9 76
2 7
1 2 29
2 1
2 2
2 9
2 2
2 5
1 3 85
1 1 64
1 2 36
1 5 100
1 6 15
1 5 48
1 1 22
2 10
2 10
2...

output:

result:

ok 99574 numbers

Test #24:

score: 0

Accepted

time: 38ms

memory: 9364kb

input:

10 100 99995
2 2
2 9
2 2
2 2
1 8 88
1 6 21
2 9
2 1
2 5
2 8
1 6 59
1 9 2
2 4
2 10
2 7
1 7 89
2 3
1 7 26
2 2
2 2
2 2
2 7
2 2
2 5
2 4
2 10
1 5 44
2 1
2 8
1 2 76
1 3 55
2 9
2 3
2 6
1 2 86
1 5 99
2 10
2 6
2 5
1 3 19
1 1 38
2 4
2 6
2 10
2 5
1 7 52
1 7 34
2 2
2 3
2 1
2 7
2 2
2 3
2 8
2 10
1 4 57
2 1
1 6 62
...

output:

result:

ok 99576 numbers

Test #25:

score: 0

Accepted

time: 1ms

memory: 8344kb

input:

output:

result:

ok 12 numbers

Test #26:

score: 0

Accepted

time: 1ms

memory: 10136kb

input:

3 100000 20
1 1 59705
2 3
1 1 96861
2 3
1 2 35329
1 2 13432
2 3
1 2 42574
2 1
2 2
2 2
1 2 32127
2 1
2 1
1 1 42623
1 1 83967
2 1
2 1
2 3
2 3

output:

result:

ok 12 numbers

Test #27:

score: 0

Accepted

time: 1ms

memory: 9700kb

input:

output:

result:

ok 12 numbers

Test #28:

score: 0

Accepted

time: 11ms

memory: 9724kb

input:

output:

result:

ok 99976 numbers

Test #29:

score: 0

Accepted

time: 317ms

memory: 13520kb

input:

10 100000 99997
2 5
1 1 68198
1 6 4509
1 5 74543
1 7 68437
1 8 63663
2 10
2 10
1 4 62195
2 3
1 9 12291
1 3 33708
1 6 65787
2 9
1 3 46161
2 5
1 3 48563
1 8 78539
2 3
2 9
1 5 20498
1 1 98009
2 8
2 4
1 1 97669
2 7
1 1 66304
2 1
1 4 34460
2 2
1 1 89591
2 1
2 6
2 6
2 6
2 3
1 8 75468
1 6 37258
2 10
2 3
2 ...

output:

result:

ok 53532 numbers

Test #30:

score: 0

Accepted

time: 101ms

memory: 327500kb

input:

100000 100 99997
2 91323
2 51108
1 58111 68
1 23338 77
2 38318
2 10972
1 12004 3
1 72923 96
1 26225 17
2 93537
1 41660 79
1 92069 66
1 20590 2
2 94199
2 51099
2 92961
2 40675
2 68687
1 94317 32
2 94120
2 30949
2 63348
1 84520 32
2 48766
1 59124 59
1 4711 69
2 7426
1 31122 59
2 42307
2 75291
2 78272
...

output:

result:

ok 50427 numbers

Test #31:

score: 0

Accepted

time: 0ms

memory: 10884kb

input:

200 100000 20
1 130 75919
1 58 48816
2 97
1 42 57280
1 143 99525
1 52 55647
2 31
2 19
2 10
2 97
1 179 19505
2 168
1 125 80275
2 112
2 45
2 35
1 36 84431
2 41
2 5
1 146 21446

output:

result:

ok 11 numbers

Test #32:

score: 0

Accepted

time: 0ms

memory: 9984kb

input:

200 200 444
2 165
2 71
2 84
1 49 199
2 31
2 57
2 165
2 123
1 52 67
2 147
2 80
1 163 138
2 36
2 189
2 74
2 159
1 88 131
2 127
1 198 67
1 31 86
2 77
2 61
2 172
2 15
2 26
1 76 107
1 61 180
1 197 163
2 198
1 35 8
2 177
2 172
2 144
2 189
1 8 171
1 75 93
2 100
2 197
1 86 114
2 46
1 151 13
1 107 145
2 97
2...

output:

result:

ok 228 numbers

Test #33:

score: 0

Accepted

time: 2ms

memory: 9804kb

input:

200 200 444
1 50 156
2 178
1 115 172
1 19 105
2 15
1 65 80
1 97 10
2 21
2 114
1 61 164
1 110 197
2 189
1 45 183
2 118
1 37 137
1 86 185
2 68
2 38
2 164
2 177
1 141 84
1 63 47
2 16
2 88
2 54
2 46
2 166
1 136 161
2 23
2 161
2 82
1 154 88
2 156
2 183
2 182
2 150
2 37
2 78
1 90 156
2 126
2 178
2 136
2 1...

output:

result:

ok 228 numbers

Test #34:

score: 0

Accepted

time: 5ms

memory: 9040kb

input:

output:

result:

ok 5158 numbers

Test #35:

score: 0

Accepted

time: 0ms

memory: 9732kb

input:

3 99998 444
1 2 86573
1 2 47858
1 2 7363
1 2 4551
1 2 85360
2 3
2 3
2 3
1 1 60369
2 2
1 1 95442
1 1 28660
2 2
2 3
2 2
1 1 95208
1 2 51304
2 1
1 2 24560
2 3
2 3
2 2
1 2 82898
1 2 47967
1 2 24593
2 2
2 3
1 1 34839
2 3
1 1 42124
2 2
2 2
2 3
2 2
2 2
1 1 4830
1 2 4347
1 1 14759
1 2 67945
2 2
2 3
1 2 5506...

output:

result:

ok 217 numbers

Test #36:

score: 0

Accepted

time: 234ms

memory: 11280kb

input:

3 99998 66666
1 2 83216
1 1 63804
1 2 48420
2 3
1 2 30485
2 2
1 1 27694
2 2
2 3
2 3
1 2 22881
2 1
2 3
1 1 92867
2 1
2 1
1 2 18779
1 1 62209
1 2 80552
2 1
2 1
2 1
2 3
1 2 15526
1 2 2802
2 1
1 2 15860
2 3
1 2 92264
1 2 22376
2 3
1 2 82784
2 1
1 2 73935
2 2
2 3
1 2 22700
1 2 37392
2 3
2 3
2 2
1 2 49108...

output:

result:

ok 38353 numbers

Test #37:

score: 0

Accepted

time: 11ms

memory: 9408kb

input:

3 99998 5555
1 1 17894
1 2 37810
2 1
2 1
2 1
2 3
2 2
1 2 31737
1 1 53853
2 3
2 2
1 1 28771
2 1
2 1
1 1 31845
1 1 86225
2 1
1 2 65732
1 1 6390
1 2 56602
1 2 44026
1 2 18330
1 1 34750
2 3
1 1 77984
1 1 5571
2 3
1 2 89815
1 2 63607
2 1
1 1 23160
1 2 94025
2 1
1 2 19803
2 2
2 1
2 2
2 3
1 2 32407
2 1
2 3...

output:

result:

ok 2837 numbers

Test #38:

score: 0

Accepted

time: 278ms

memory: 13936kb

input:

50 99997 100000
2 15
2 1
1 5 460
2 16
2 33
1 26 22817
1 32 57730
1 12 49344
2 24
1 48 78596
1 2 4273
2 2
1 31 92410
1 18 11945
2 22
2 3
1 2 47838
1 5 66084
1 3 51032
2 48
1 3 73823
2 11
1 44 69177
2 41
1 3 67803
1 1 41983
2 29
1 5 4984
1 3 14926
1 1 19550
1 4 23996
2 2
1 2 55552
2 9
2 41
2 13
1 20 1...

output:

result:

ok 51923 numbers

Test #39:

score: 0

Accepted

time: 287ms

memory: 14380kb

input:

50 99997 100000
1 5 91754
2 31
1 5 49396
2 37
2 1
1 2 49833
2 1
2 32
1 36 58423
2 36
2 48
1 48 57743
1 44 13519
1 3 34770
2 25
2 18
1 33 4593
2 28
2 24
1 1 89841
1 18 16369
1 1 86567
1 3 21985
2 23
2 18
1 39 21575
1 4 885
1 30 9434
1 26 82438
2 35
1 5 74679
2 47
1 10 49171
2 11
2 32
1 6 58414
2 4
1 ...

output:

result:

ok 52287 numbers

Test #40:

score: 0

Accepted

time: 279ms

memory: 13944kb

input:

50 99997 100000
2 28
2 43
1 2 37572
2 17
1 16 22203
1 5 28006
1 3 69631
2 50
2 39
2 31
1 33 52184
2 48
1 2 88889
2 37
1 3 54786
1 2 89816
1 2 61584
1 2 1804
1 1 46769
1 5 50489
2 44
1 3 49339
1 40 18496
2 43
2 49
2 50
2 45
1 40 56707
2 38
2 50
1 23 84774
2 42
2 18
1 1 24812
2 22
1 24 55916
1 9 60712...

output:

result:

ok 51939 numbers

Test #41:

score: 0

Accepted

time: 278ms

memory: 13768kb

input:

50 99997 100000
1 33 68534
2 47
2 45
1 32 728
2 48
1 4 92826
2 1
2 46
2 24
1 5 77867
1 5 81166
1 12 61775
2 48
2 21
1 16 2654
1 5 41711
2 37
2 24
2 2
1 1 95552
2 12
1 2 50935
2 48
1 3 22987
1 1 745
2 48
2 6
1 2 82254
2 4
1 3 73148
1 2 58653
2 8
1 28 60585
2 42
1 41 6721
1 41 61606
1 2 89435
2 43
2 3...

output:

result:

ok 51759 numbers