QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#623095#8404. Modernizacja Bajtocji [A]chenxinyang20061 184ms30664kbC++202.1kb2024-10-09 10:09:472024-10-09 10:09:47

Judging History

This is the latest submission verdict.

  • [2024-10-09 10:09:47]
  • Judged
  • Verdict: 1
  • Time: 184ms
  • Memory: 30664kb
Show
  • [2024-10-09 10:09:47]
  • Submitted

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n,m,q;
int col[300005],tag[1300005],siz[300005];
vector <int> S[1300005];
char str[5];

void mrg(int u,int v){
	if(col[u] == col[v]){
		assert(!tag[col[u]]);
		tag[col[u]] = 1;
		return;
	}
	if(siz[col[u]] < siz[col[v]]) swap(u,v);
	for(int p:S[col[v]]){
		if(col[p] != col[v]) continue;
		col[p] = col[u];
		S[col[u]].eb(p);
	}
	tag[col[u]] |= tag[col[v]];
	S[col[v]].clear();
	S[col[v]].shrink_to_fit();
	siz[col[u]] += siz[col[v]];
}

void cut(int u){
	siz[col[u]]--;
	col[u] = ++m;
	tag[m] = 0;siz[m] = 1;
	S[m].eb(u);
}

void query(int u){
	if(tag[col[u]]) printf("1");
	else if(siz[col[u]] == 1) printf("0");
	else printf("?");
}

void dbg(){
	rep(u,1,n) printf("%d ",col[u]);
	printf("\n");
	rep(i,1,m) printf("group %d siz %d tag %d\n",i,siz[i],tag[i]);
}

int main(){	
//	freopen("test.in","r",stdin);
	scanf("%d%d",&n,&q);
	rep(u,1,n){
		col[u] = u;
		tag[u] = 0;
		siz[u] = 1;
		S[u].eb(u);
	}
	m = n;
	int u,v;
	rep(i,1,q){
		scanf("%s",str + 1);
		scanf("%d",&u);
		if(str[1] == '+'){
			scanf("%d",&v);
			mrg(u,v);
		}else if(str[1] == '-'){
			cut(u);
		}else{
			query(u);
		}
//		dbg();
	}
	printf("\n");
	return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 2ms
memory: 5936kb

input:

1 1
? 1

output:

0

result:

ok single line: '0'

Test #2:

score: 1
Accepted
time: 3ms
memory: 9984kb

input:

1 3
? 1
+ 1 1
? 1

output:

01

result:

ok single line: '01'

Test #3:

score: 1
Accepted
time: 2ms
memory: 5932kb

input:

2 10
+ 2 1
+ 1 1
? 1
- 1
+ 2 1
? 1
? 1
- 1
? 2
? 2

output:

11111

result:

ok single line: '11111'

Test #4:

score: 1
Accepted
time: 2ms
memory: 5932kb

input:

4 20
+ 1 3
+ 3 3
? 2
? 3
? 2
+ 1 4
- 4
- 1
+ 4 1
? 1
? 4
? 1
? 1
? 4
+ 4 2
? 4
- 4
- 1
? 3
+ 2 1

output:

010??????1

result:

ok single line: '010??????1'

Test #5:

score: 1
Accepted
time: 2ms
memory: 7980kb

input:

10 20
? 6
+ 1 7
+ 6 7
? 7
? 1
+ 7 7
+ 6 2
? 4
? 5
? 6
? 3
- 2
+ 3 8
+ 4 1
+ 7 8
? 7
+ 4 2
? 1
? 7
- 1

output:

0??0010111

result:

ok single line: '0??0010111'

Test #6:

score: 1
Accepted
time: 2ms
memory: 5876kb

input:

10 20
+ 2 9
+ 5 2
+ 1 4
? 3
? 1
+ 6 2
? 3
+ 6 8
- 4
+ 4 6
+ 6 10
- 9
- 5
- 4
+ 6 2
- 8
+ 8 2
? 5
+ 4 8
+ 7 8

output:

0?00

result:

ok single line: '0?00'

Test #7:

score: 1
Accepted
time: 2ms
memory: 5940kb

input:

10 18
? 1
+ 8 1
+ 6 2
? 10
+ 2 4
+ 9 8
? 5
+ 3 9
? 8
? 8
? 8
? 5
+ 10 3
? 2
? 3
? 3
- 3
- 2

output:

000???0???

result:

ok single line: '000???0???'

Test #8:

score: 1
Accepted
time: 0ms
memory: 9900kb

input:

10 19
? 6
? 7
? 9
+ 10 10
+ 10 1
+ 1 9
+ 8 9
+ 2 5
+ 5 4
- 8
- 9
? 8
? 6
+ 2 2
- 5
+ 8 6
- 1
? 10
+ 7 4

output:

000001

result:

ok single line: '000001'

Test #9:

score: 1
Accepted
time: 2ms
memory: 5884kb

input:

10 20
? 6
+ 2 8
+ 5 1
+ 6 1
+ 7 5
+ 8 1
- 2
+ 6 4
? 6
+ 5 1
? 1
? 2
- 5
- 8
- 7
? 5
? 8
+ 1 5
? 7
? 2

output:

0?100000

result:

ok single line: '0?100000'

Subtask #2:

score: 0
Wrong Answer

Test #10:

score: 0
Wrong Answer
time: 2ms
memory: 9968kb

input:

29 97
+ 7 20
? 26
+ 10 16
? 18
? 8
? 27
? 19
+ 29 20
? 7
+ 1 19
? 6
? 21
? 7
+ 28 9
+ 27 2
? 2
+ 20 18
? 5
+ 25 22
+ 7 13
+ 17 29
? 6
+ 9 15
+ 13 22
? 24
? 12
? 24
+ 2 13
- 29
+ 7 11
? 7
? 1
+ 7 8
- 16
- 7
+ 18 17
+ 28 20
? 10
+ 4 12
? 1
? 16
? 7
? 7
? 19
+ 12 22
? 18
? 20
? 6
? 27
+ 7 24
+ 22 7
? 1...

output:

00000?00??00000??0?000?110?100?111??01??0

result:

wrong answer 1st lines differ - expected: '00000?00??00000??0?000?110110011111101110', found: '00000?00??00000??0?000?110?100?111??01??0'

Subtask #3:

score: 0
Wrong Answer

Test #20:

score: 0
Wrong Answer
time: 2ms
memory: 9988kb

input:

99 391
? 44
+ 54 43
? 63
? 90
+ 91 19
? 93
+ 74 55
? 37
? 39
+ 21 5
+ 25 91
+ 27 30
? 83
+ 53 65
+ 38 64
? 33
- 21
? 37
- 30
+ 91 17
+ 10 83
? 9
? 87
? 41
? 30
+ 34 55
+ 90 78
? 22
? 73
? 54
? 80
+ 67 56
+ 24 87
+ 38 60
? 94
? 43
? 40
- 56
? 40
+ 12 27
- 27
? 23
? 5
+ 3 44
+ 72 85
? 73
+ 13 63
- 34
...

output:

000000000000000?00?00000?0000??000000000??????00?0?0??0?0?0000?00???0??00000???0?0??0000???0?0?0?0????00?00?0???000?0?????0?0????0???00000000??????00????0??0?00??0?0????0000????0?????

result:

wrong answer 1st lines differ - expected: '000000000000000?00?00000?0000?...?1110100110?0111?10001111111?11', found: '000000000000000?00?00000?0000?...?0??0?00??0?0????0000????0?????'

Subtask #4:

score: 0
Wrong Answer

Test #37:

score: 0
Wrong Answer
time: 0ms
memory: 5836kb

input:

300 924
? 59
+ 231 295
? 106
? 132
? 106
? 145
+ 100 196
? 118
- 100
? 59
? 291
+ 93 119
? 293
+ 179 99
+ 226 69
? 256
? 285
? 226
+ 58 155
? 190
+ 2 90
+ 241 78
? 69
? 239
+ 94 251
? 59
? 297
+ 115 267
? 65
+ 279 106
+ 183 154
? 145
+ 180 254
+ 147 285
? 203
? 186
+ 85 106
? 250
+ 196 210
? 283
? 1...

output:

00000000000?0?000000000000000000?0?0?000?00?00?0000000000000000?0??00?0??0??0?000000000?000?0?00?000?00?0?0?0000???00000?000?0?000?0?00?0?00000???000?00000?0?????00?0????0??0?000??0??0?0?????0?0??00???????0?0?000????????00???0?0?????000?0?0?000?0??00??0?0??????0000???0?00?0?????????0?00??00???????0?...

result:

wrong answer 1st lines differ - expected: '00000000000?0?0000000000000000...101000?011000011011?10010110110', found: '00000000000?0?0000000000000000...?0?000?0???000??0????00?0??00?0'

Subtask #5:

score: 0
Wrong Answer

Test #54:

score: 0
Wrong Answer
time: 0ms
memory: 8192kb

input:

3000 9744
+ 2240 1376
+ 552 2967
+ 380 2865
+ 25 1339
+ 1688 1131
? 2317
? 2045
? 2295
? 668
+ 2098 2242
+ 179 1859
? 1516
+ 2577 456
? 1657
? 938
? 274
? 2337
+ 1490 1394
+ 1923 2049
+ 707 497
+ 514 1068
+ 2309 2966
+ 2044 1946
? 499
? 700
+ 2426 2362
+ 1094 561
? 1183
? 2456
+ 1630 1005
+ 2528 264...

output:

00000000000000000000000000000000000000000000000000000000000000?00?000000000000000000000000?0?00000000000000?????00?0000?0000?000000000000?0?00000000?0000000000000000000?000000000?0000?0000000000000000000000?000000000?00000000000?000?00??00?000000?000?0000000000000000000000000?0000?0?000000000000?000...

result:

wrong answer 1st lines differ - expected: '000000000000000000000000000000...110111110111?1?1000?10100101001', found: '000000000000000000000000000000...??00????0???????000??0?0000??0?'

Subtask #6:

score: 0
Wrong Answer

Test #72:

score: 0
Wrong Answer
time: 31ms
memory: 11980kb

input:

50000 156785
? 7574
+ 23871 49430
? 34700
+ 46209 6266
+ 6220 25627
? 46445
+ 17407 32424
? 31750
? 39616
? 41616
+ 6724 49194
+ 30434 21574
? 7469
? 37204
? 39060
? 25290
? 40330
? 15428
+ 44101 7852
+ 18662 34969
+ 11556 17270
? 10132
+ 31134 48464
+ 24700 43615
+ 12173 26470
+ 27682 13463
+ 39534...

output:

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

wrong answer 1st lines differ - expected: '000000000000000000000000000000...10?001?1011?0?001111100110??110', found: '000000000000000000000000000000...?0??0???0???0?00?????00??0????0'

Subtask #7:

score: 0
Wrong Answer

Test #90:

score: 0
Wrong Answer
time: 78ms
memory: 16504kb

input:

89220 376231
? 6393
+ 51619 6393
+ 2246 25592
? 62228
? 44401
+ 42111 52472
+ 30667 77472
+ 11532 88363
+ 18526 57345
+ 16738 67835
+ 29960 30391
? 54
? 87927
? 85856
? 18958
? 31978
? 37673
? 29050
+ 19474 60497
? 88112
? 15348
+ 68377 78220
? 75153
+ 53534 18315
? 71265
+ 3148 60288
+ 40013 38591
...

output:

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

wrong answer 1st lines differ - expected: '000000000000000000000000000000...01100011001110001100100?0000010', found: '000000000000000000000000000000...00?000??00???000?000?00?00000?0'

Subtask #8:

score: 0
Wrong Answer

Test #108:

score: 0
Wrong Answer
time: 132ms
memory: 21668kb

input:

150000 585478
+ 78237 9254
? 59202
+ 51044 85838
+ 149256 127083
? 2631
? 30730
+ 70219 104852
? 146465
? 140150
? 77737
? 144566
? 136963
+ 66495 149103
+ 87466 109146
+ 94625 57390
+ 38604 104025
+ 53471 30696
+ 19225 40513
+ 5834 40766
? 145472
+ 111565 102244
? 114750
? 65515
? 140591
+ 110486 3...

output:

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

wrong answer 1st lines differ - expected: '000000000000000000000000000000...01000?1110010111101110100?00001', found: '000000000000000000000000000000...0?000?0??0000????0???0??0?0000?'

Subtask #9:

score: 0
Wrong Answer

Test #126:

score: 0
Wrong Answer
time: 184ms
memory: 30664kb

input:

220000 779870
+ 126216 50788
? 35985
+ 90827 44708
+ 186024 41018
? 12989
+ 67142 23771
? 45410
+ 20498 97233
+ 204142 90473
? 194076
+ 64537 65999
? 7877
? 217242
+ 188179 16486
? 171613
? 25863
+ 35528 203476
? 194601
+ 133835 119714
+ 147686 4608
+ 117115 37828
? 22591
? 82495
+ 51325 20964
? 876...

output:

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

wrong answer 1st lines differ - expected: '000000000000000000000000000000...1101101?0111?111101010101011101', found: '000000000000000000000000000000...010?10??01?1????101010?0101100?'

Subtask #10:

score: 0
Runtime Error

Test #144:

score: 0
Runtime Error

input:

299108 992636
+ 229230 1966
+ 141316 98248
+ 14432 125630
+ 29064 28258
? 174127
? 213753
? 22485
+ 60064 160159
? 128830
? 110504
? 162839
+ 179310 116614
+ 106734 260292
+ 187972 6883
+ 246144 102185
+ 79391 39735
+ 119136 17345
? 110239
+ 209222 110862
? 173920
? 2143
? 269421
? 7375
? 111474
? 2...

output:

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:
English 繁體中文 简体中文

Server Time: 2025-02-09 04:03:18 | OpenSource Project