QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#623128	#8404. Modernizacja Bajtocji [A]	chenxinyang2006	0	28ms	13812kb	C++20	2.1kb	2024-10-09 10:18:20	2024-10-09 10:18:21

Judging History

This is the latest submission verdict.

[2024-10-09 10:18:21]
Judged

Verdict: 0
Time: 28ms
Memory: 13812kb

Show

[2024-10-09 10:18:20]
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[1300005];
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);
	}
	assert(!tag[col[u]] || !tag[col[v]]);
	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;
}

源文件, 语言: C++20

詳細信息

Subtask #1:

score: 0

Runtime Error

Test #1:

score: 1

Accepted

time: 0ms

memory: 7836kb

input:

1 1
? 1

output:

result:

ok single line: '0'

Test #2:

score: 1

Accepted

time: 3ms

memory: 10024kb

input:

output:

result:

ok single line: '01'

Test #3:

score: 0

Runtime Error

input:

output:

result:

Subtask #2:

score: 0

Runtime Error

Test #10:

score: 0

Runtime Error

input:

output:

result:

Subtask #3:

score: 0

Wrong Answer

Test #20:

score: 0

Wrong Answer

time: 3ms

memory: 7900kb

input:

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: 3ms

memory: 9892kb

input:

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

Runtime Error

Test #54:

score: 0

Runtime Error

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:

result:

Subtask #6:

score: 0

Wrong Answer

Test #72:

score: 0

Wrong Answer

time: 28ms

memory: 13812kb

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

Runtime Error

Test #90:

score: 0

Runtime Error

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:

Subtask #8:

score: 0

Runtime Error

Test #108:

score: 0

Runtime Error

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:

Subtask #9:

score: 0

Runtime Error

Test #126:

score: 0

Runtime Error

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:

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...