QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#588283	#8809. Telephone Plans	chenxinyang2006^#	5	1ms	3988kb	C++20	2.2kb	2024-09-25 09:01:09	2024-09-25 09:01:11

Judging History

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

[2024-09-25 09:01:11]
评测

测评结果：5
用时：1ms
内存：3988kb

查看

[2024-09-25 09:01:09]
提交

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 online;
int n,m,q;
int _u[2005],_v[2005];

struct solver{
	int m;
	int _u[2005],_v[2005];
	void link(int u,int v){
		++m;
		_u[m] = u;_v[m] = v;
	}
	void cut(int u,int v){
		rep(i,1,m) if((_u[i] == u && _v[i] == v) || (_u[i] == v && _v[i] == u)) _u[i] = _v[i] = 0;
	}

	int fa[2005],siz[2005];
	int fnd(int u){
		if(fa[u] == u) return u;
		return fa[u] = fnd(fa[u]);
	}
	void mrg(int u,int v){
		u = fnd(u);v = fnd(v);
		if(u == v) return;
		fa[u] = v; 
		siz[v] += siz[u];
	}
	ll query(){
		rep(u,1,n){
			fa[u] = u;
			siz[u] = 1;
		}
		rep(i,1,m){
			if(!_u[i]) continue;
			mrg(_u[i],_v[i]);
		}
		ll ret = 0;
		rep(u,1,n) if(fa[u] == u) ret += 1ll * siz[u] * (siz[u] - 1) / 2;
		return ret;
	}
}P,Q;
ll a[2005],b[2005];
ll calc(int l,int r){
	ll sum = 0;
	rep(i,l,r) sum += a[i];
	rep(i,l + 1,r) sum -= b[i];
	return sum;
}

int main(){	
//	freopen("test.in","r",stdin);
	scanf("%d%d%d",&online,&n,&q);
	int op;
	ll x,y,lastans = 0;
	rep(i,1,q){
		scanf("%d%lld",&op,&x);
		if(op < 3) scanf("%lld",&y);
		if(online){
			x ^= lastans;
			y ^= lastans;
		}
		if(op == 1){
			P.link(x,y);
		}else if(op == 2){
			P.cut(x,y);
			Q.cut(x,y);
		}
		a[i] = P.query();b[i] = Q.query();
		if(op == 1) Q.link(x,y);
		if(op == 3){
			lastans = calc(i - x,i);
			printf("%lld\n",lastans);
		}
	}
	return 0;
}

源文件, 语言: C++20

詳細信息

Subtask #1:

score: 3

Accepted

Test #1:

score: 3

Accepted

time: 0ms

memory: 3964kb

input:

output:

result:

ok 147 lines

Test #2:

score: 3

Accepted

time: 0ms

memory: 3984kb

input:

output:

result:

ok 8 lines

Test #3:

score: 3

Accepted

time: 0ms

memory: 3880kb

input:

output:

result:

ok 92 lines

Test #4:

score: 3

Accepted

time: 0ms

memory: 3932kb

input:

output:

result:

ok 92 lines

Test #5:

score: 3

Accepted

time: 0ms

memory: 3944kb

input:

output:

result:

ok 92 lines

Test #6:

score: 3

Accepted

time: 1ms

memory: 3864kb

input:

output:

result:

ok 92 lines

Test #7:

score: 3

Accepted

time: 1ms

memory: 3980kb

input:

output:

result:

ok 92 lines

Test #8:

score: 3

Accepted

time: 1ms

memory: 3796kb

input:

output:

result:

ok 92 lines

Test #9:

score: 3

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok 92 lines

Test #10:

score: 3

Accepted

time: 0ms

memory: 3984kb

input:

output:

result:

ok 92 lines

Test #11:

score: 3

Accepted

time: 0ms

memory: 3916kb

input:

output:

result:

ok 92 lines

Test #12:

score: 3

Accepted

time: 0ms

memory: 3920kb

input:

output:

result:

ok 92 lines

Test #13:

score: 3

Accepted

time: 0ms

memory: 3988kb

input:

output:

result:

ok 92 lines

Test #14:

score: 3

Accepted

time: 0ms

memory: 3936kb

input:

output:

result:

ok 92 lines

Test #15:

score: 3

Accepted

time: 0ms

memory: 3924kb

input:

output:

result:

ok 92 lines

Test #16:

score: 3

Accepted

time: 0ms

memory: 3988kb

input:

output:

result:

ok 92 lines

Test #17:

score: 3

Accepted

time: 0ms

memory: 3984kb

input:

output:

result:

ok 92 lines

Test #18:

score: 3

Accepted

time: 0ms

memory: 3864kb

input:

output:

result:

ok 92 lines

Test #19:

score: 3

Accepted

time: 0ms

memory: 3980kb

input:

output:

result:

ok 92 lines

Test #20:

score: 3

Accepted

time: 0ms

memory: 3936kb

input:

output:

result:

ok 92 lines

Test #21:

score: 3

Accepted

time: 0ms

memory: 3984kb

input:

output:

result:

ok 94 lines

Test #22:

score: 3

Accepted

time: 0ms

memory: 3916kb

input:

output:

result:

ok 93 lines

Test #23:

score: 3

Accepted

time: 0ms

memory: 3804kb

input:

output:

result:

ok 92 lines

Test #24:

score: 3

Accepted

time: 0ms

memory: 3944kb

input:

output:

result:

ok 92 lines

Test #25:

score: 3

Accepted

time: 0ms

memory: 3980kb

input:

output:

result:

ok 92 lines

Test #26:

score: 3

Accepted

time: 0ms

memory: 3872kb

input:

output:

result:

ok 92 lines

Test #27:

score: 3

Accepted

time: 0ms

memory: 3980kb

input:

output:

result:

ok 139 lines

Test #28:

score: 3

Accepted

time: 0ms

memory: 3936kb

input:

output:

result:

ok 149 lines

Subtask #2:

score: 2

Accepted

Test #29:

score: 2

Accepted

time: 0ms

memory: 3864kb

input:

output:

result:

ok 147 lines

Test #30:

score: 2

Accepted

time: 0ms

memory: 3872kb

input:

output:

result:

ok 8 lines

Test #31:

score: 2

Accepted

time: 0ms

memory: 3940kb

input:

output:

result:

ok 92 lines

Test #32:

score: 2

Accepted

time: 0ms

memory: 3844kb

input:

output:

result:

ok 92 lines

Test #33:

score: 2

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok 92 lines

Test #34:

score: 2

Accepted

time: 0ms

memory: 3980kb

input:

output:

result:

ok 92 lines

Test #35:

score: 2

Accepted

time: 0ms

memory: 3876kb

input:

output:

result:

ok 92 lines

Test #36:

score: 2

Accepted

time: 0ms

memory: 3920kb

input:

output:

result:

ok 92 lines

Test #37:

score: 2

Accepted

time: 0ms

memory: 3920kb

input:

output:

result:

ok 92 lines

Test #38:

score: 2

Accepted

time: 0ms

memory: 3980kb

input:

output:

result:

ok 92 lines

Test #39:

score: 2

Accepted

time: 0ms

memory: 3980kb

input:

output:

result:

ok 92 lines

Test #40:

score: 2

Accepted

time: 0ms

memory: 3928kb

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

memory: 3804kb

input:

output:

result:

ok 92 lines

Test #42:

score: 2

Accepted

time: 0ms

memory: 3940kb

input:

output:

result:

ok 92 lines

Test #43:

score: 2

Accepted

time: 0ms

memory: 3924kb

input:

output:

result:

ok 92 lines

Test #44:

score: 2

Accepted

time: 0ms

memory: 3852kb

input:

output:

result:

ok 92 lines

Test #45:

score: 2

Accepted

time: 0ms

memory: 3804kb

input:

output:

result:

ok 92 lines

Test #46:

score: 2

Accepted

time: 0ms

memory: 3932kb

input:

output:

result:

ok 92 lines

Test #47:

score: 2

Accepted

time: 0ms

memory: 3932kb

input:

output:

result:

ok 92 lines

Test #48:

score: 2

Accepted

time: 0ms

memory: 3940kb

input:

output:

result:

ok 92 lines

Test #49:

score: 2

Accepted

time: 0ms

memory: 3860kb

input:

output:

result:

ok 94 lines

Test #50:

score: 2

Accepted

time: 0ms

memory: 3852kb

input:

output:

result:

ok 93 lines

Test #51:

score: 2

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok 92 lines

Test #52:

score: 2

Accepted

time: 0ms

memory: 3852kb

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

memory: 3984kb

input:

output:

result:

ok 92 lines

Test #54:

score: 2

Accepted

time: 0ms

memory: 3932kb

input:

output:

result:

ok 92 lines

Test #55:

score: 2

Accepted

time: 0ms

memory: 3856kb

input:

output:

result:

ok 139 lines

Test #56:

score: 2

Accepted

time: 0ms

memory: 3780kb

input:

output:

result:

ok 149 lines

Subtask #3:

score: 0

Runtime Error

Dependency #1:

100%

Accepted

Test #57:

score: 0

Runtime Error

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:

Subtask #4:

score: 0

Runtime Error

Dependency #2:

100%

Accepted

Test #80:

score: 0

Runtime Error

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:

Subtask #5:

score: 0

Skipped

Dependency #3:

Subtask #6:

score: 0

Skipped

Dependency #4:

Subtask #7:

score: 0

Skipped