QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#424102	#8109. Postcards	DaiRuiChen007	AC ✓	598ms	50392kb	C++14	2.2kb	2024-05-28 21:51:29	2024-05-28 21:51:30

Judging History

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

[2024-05-28 21:51:30]
评测

测评结果：AC
用时：598ms
内存：50392kb

查看

[2024-05-28 21:51:29]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3005,MAXM=5e5+5,MAXR=105;
struct Edge {
	int u,v;
}	E[MAXM];
int n,m,q,lst=0;
int o[MAXN][MAXN],w[MAXR][MAXR],Q[MAXR],nw[MAXR][2];
bitset <MAXR> in[MAXR];
int fa[MAXN],L[MAXN],dfn[MAXN],R[MAXN],dc;
int siz[MAXN],sz[MAXR];
vector <int> G[MAXN],g[MAXR];
void dfs0(int u,int fz) {
	fa[u]=fz,dfn[u]=L[u]=++dc,siz[u]=1;
	for(int v:G[u]) if(!dfn[v]) dfs0(v,u),siz[u]+=siz[v];
	R[u]=dc;
}
bool cont(int x,int y) { return L[x]<=L[y]&&R[y]<=R[x]; }
void dfs1(int u) {
	for(int v:G[u]) if(fa[v]==u) {
		dfs1(v);
		for(int i=1;i<=n;++i) o[u][i]+=o[v][i];
	}
}
void dfs2(int u) {
	for(int v:G[u]) if(fa[v]==u) {
		dfs2(v);
		for(int i=1;i<=n;++i) o[i][u]+=o[i][v];
	}
}
int rt[MAXR];
void solve() {
	int s,k=0;
	scanf("%d",&s);
	for(int i=1;i<=s;++i) {
		scanf("%d%d%d",&Q[i],&nw[i][0],&nw[i][1]),Q[i]=(Q[i]+lst)%m+1;
		Edge e=E[Q[i]];
		if(fa[e.v]==e.u) rt[++k]=e.v;
		else if(fa[e.u]==e.v) rt[++k]=e.u;
	}
	rt[++k]=1;
	sort(rt+1,rt+k+1,[&](int x,int y){ return dfn[x]<dfn[y]; });
	for(int i=1;i<=k;++i) in[i].reset(),g[i].clear();
	auto qid=[&](int x) {
		for(int i=k;i;--i) if(cont(rt[i],x)) return i;
		return -1;
	};
	for(int i=1;i<=k;++i) {
		g[qid(fa[rt[i]])].push_back(i);
	}
	for(int i=1;i<=k;++i) for(int j=1;j<=k;++j) {
		int &v=w[i][j]=o[rt[i]][rt[j]];
		for(int x:g[i]) v-=o[rt[x]][rt[j]];
		for(int y:g[j]) v-=o[rt[i]][rt[y]];
		for(int x:g[i]) for(int y:g[j]) v+=o[rt[x]][rt[y]];
	}
	for(int i=1;i<=k;++i) {
		sz[i]=siz[rt[i]];
		for(int j:g[i]) sz[i]-=siz[rt[j]];
	}
	for(int i=1;i<=s;++i) {
		Edge e=E[Q[i]];
		int x=qid(e.u),y=qid(e.v);
		if(nw[i][0]) --w[x][y];
		if(nw[i][1]) --w[y][x];
	}
	for(int i=1;i<=k;++i) for(int j=1;j<=k;++j) if(w[i][j]||i==j) in[j].set(i);
	for(int i=1;i<=k;++i) for(int j=1;j<=k;++j) if(in[j][i]) in[j]|=in[i];
	int ans=0;
	for(int i=1;i<=k;++i) if((int)in[i].count()==k) ans+=sz[i];
	printf("%d\n",ans);
	lst=(lst+ans)%m;
}
signed main() {
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1,u,v;i<=m;++i) {
		scanf("%d%d",&u,&v),E[i]={u,v};
		++o[u][v],++o[v][u];
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs0(1,0),dfs1(1),dfs2(1);
	while(q--) solve();
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 6216kb

input:

output:

3
1
0

result:

ok 3 number(s): "3 1 0"

Test #2:

score: 0

Accepted

time: 183ms

memory: 41976kb

input:

3000 11860 5000
135 1279
1379 1627
1253 2516
338 1596
260 1086
1153 2182
527 732
500 2820
1395 1556
793 1491
2673 2746
1630 1792
1720 2871
443 2095
1095 1296
2008 2358
1685 1801
2356 2704
1856 2698
1798 2134
1683 1792
812 2977
43 1507
1297 1574
222 1563
1278 2168
1181 1851
1492 2757
432 1459
428 902...

output:

result:

ok 5000 numbers

Test #3:

score: 0

Accepted

time: 150ms

memory: 44252kb

input:

2430 490875 33333
2 1
3 1
3 2
4 1
4 2
4 3
5 1
5 2
5 3
5 4
6 1
6 2
6 3
6 4
6 5
7 1
7 2
7 3
7 4
7 5
7 6
8 1
8 2
8 3
8 4
8 5
8 6
8 7
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
11 1
11 2
11 3
11 4
11 5
11 6
11 7
11 8
11 9
11 10
12 1
12 2
12 3
12 4
12 5
12 6
12 7
12 8
12...

output:

result:

ok 33333 numbers

Test #4:

score: 0

Accepted

time: 148ms

memory: 39808kb

input:

2225 493960 50000
2 1
3 1
3 2
4 1
4 2
4 3
5 1
5 2
5 3
5 4
6 1
6 2
6 3
6 4
6 5
7 1
7 2
7 3
7 4
7 5
7 6
8 1
8 2
8 3
8 4
8 5
8 6
8 7
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
11 1
11 2
11 3
11 4
11 5
11 6
11 7
11 8
11 9
11 10
12 1
12 2
12 3
12 4
12 5
12 6
12 7
12 8
12...

output:

result:

ok 50000 numbers

Test #5:

score: 0

Accepted

time: 147ms

memory: 46692kb

input:

2625 490896 23809
2 1
3 1
3 2
4 1
4 2
4 3
5 1
5 2
5 3
5 4
6 1
6 2
6 3
6 4
6 5
7 1
7 2
7 3
7 4
7 5
7 6
8 1
8 2
8 3
8 4
8 5
8 6
8 7
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
11 1
11 2
11 3
11 4
11 5
11 6
11 7
11 8
11 9
11 10
12 1
12 2
12 3
12 4
12 5
12 6
12 7
12 8
12...

output:

result:

ok 23809 numbers

Test #6:

score: 0

Accepted

time: 155ms

memory: 41832kb

input:

3000 3000 250000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
...

output:

result:

ok 250000 numbers

Test #7:

score: 0

Accepted

time: 139ms

memory: 42508kb

input:

3000 13800 250000
2 1
3 1
3 2
4 1
4 2
4 3
5 1
5 2
5 3
5 4
6 1
6 2
6 3
6 4
6 5
7 1
7 2
7 3
7 4
7 5
7 6
8 1
8 2
8 3
8 4
8 5
8 6
8 7
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
12 11
13 11
13 12
14 11
14 12
14 13
15 11
15 12
15 13
15 14
16 11
16 12
16 13
16 14
16 15
17 ...

output:

result:

ok 250000 numbers

Test #8:

score: 0

Accepted

time: 179ms

memory: 50392kb

input:

3000 448510 250000
2 1
3 1
3 2
4 1
4 2
4 3
5 1
5 2
5 3
5 4
6 1
6 2
6 3
6 4
6 5
7 1
7 2
7 3
7 4
7 5
7 6
8 1
8 2
8 3
8 4
8 5
8 6
8 7
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
11 1
11 2
11 3
11 4
11 5
11 6
11 7
11 8
11 9
11 10
12 1
12 2
12 3
12 4
12 5
12 6
12 7
12 8
1...

output:

result:

ok 250000 numbers

Test #9:

score: 0

Accepted

time: 88ms

memory: 40128kb

input:

2800 9200 41666
2 1
3 1
3 2
4 1
4 2
4 3
5 1
5 2
5 3
5 4
6 1
6 2
6 3
6 4
6 5
7 1
7 2
7 3
7 4
7 5
7 6
9 8
10 8
10 9
11 8
11 9
11 10
12 8
12 9
12 10
12 11
13 8
13 9
13 10
13 11
13 12
14 8
14 9
14 10
14 11
14 12
14 13
16 15
17 15
17 16
18 15
18 16
18 17
19 15
19 16
19 17
19 18
20 15
20 16
20 17
20 18
20...

output:

result:

ok 41666 numbers

Test #10:

score: 0

Accepted

time: 98ms

memory: 40248kb

input:

2940 20972 15625
2 1
3 1
3 2
4 1
4 2
4 3
5 1
5 2
5 3
5 4
6 1
6 2
6 3
6 4
6 5
7 1
7 2
7 3
7 4
7 5
7 6
8 1
8 2
8 3
8 4
8 5
8 6
8 7
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
11 1
11 2
11 3
11 4
11 5
11 6
11 7
11 8
11 9
11 10
12 1
12 2
12 3
12 4
12 5
12 6
12 7
12 8
12 ...

output:

result:

ok 15625 numbers

Test #11:

score: 0

Accepted

time: 109ms

memory: 40752kb

input:

2809 5618 5000
1 54
1 2
2 55
2 3
3 56
3 4
4 57
4 5
5 58
5 6
6 59
6 7
7 60
7 8
8 61
8 9
9 62
9 10
10 63
10 11
11 64
11 12
12 65
12 13
13 66
13 14
14 67
14 15
15 68
15 16
16 69
16 17
17 70
17 18
18 71
18 19
19 72
19 20
20 73
20 21
21 74
21 22
22 75
22 23
23 76
23 24
24 77
24 25
25 78
25 26
26 79
26 27...

output:

result:

ok 5000 numbers

Test #12:

score: 0

Accepted

time: 84ms

memory: 6144kb

input:

20 100 12500
7 12
14 16
3 8
1 16
5 13
9 16
2 18
10 20
9 12
1 6
5 17
11 15
6 16
4 11
1 12
5 15
6 14
4 10
12 13
5 20
3 19
11 13
13 20
17 20
4 18
9 10
2 19
6 15
13 15
6 10
3 18
2 20
15 16
4 9
5 14
3 20
4 5
5 19
18 19
4 15
16 17
17 18
9 15
10 16
14 19
5 16
2 5
3 10
1 11
8 9
3 6
5 12
13 14
1 4
2 15
7 14
...

output:

result:

ok 12500 numbers

Test #13:

score: 0

Accepted

time: 97ms

memory: 6744kb

input:

output:

result:

ok 100000 numbers

Test #14:

score: 0

Accepted

time: 160ms

memory: 41816kb

input:

3000 2999 100000
32 23
1819 1600
1795 530
263 65
2688 1258
540 186
835 75
2780 1758
1483 753
859 394
387 97
100 56
616 199
824 136
1633 834
2086 789
1582 60
733 309
47 29
545 237
2418 1559
966 250
1032 929
1590 600
1980 983
2378 325
1504 1309
2583 1446
2510 976
2631 1099
1278 1264
2643 331
151 59
13...

output:

result:

ok 100000 numbers

Test #15:

score: 0

Accepted

time: 266ms

memory: 40316kb

input:

2999 2998 17857
2123 1486
1916 1560
1615 335
948 870
453 88
818 350
2502 1982
2819 1992
1333 711
1436 1282
397 362
1314 525
2926 564
94 90
2835 1610
2994 1891
2011 325
1844 211
1186 4
2006 221
1832 1700
2763 2518
607 348
2483 1077
449 352
2241 1457
2317 2149
1250 886
2180 850
1162 73
1142 1054
1118 ...

output:

result:

ok 17857 numbers

Test #16:

score: 0

Accepted

time: 598ms

memory: 40060kb

input:

2999 2998 5000
1095 1092
624 381
1167 916
2307 1155
1976 1067
584 282
2978 936
1383 247
481 279
1185 1015
2097 2008
2268 2080
393 217
1528 1417
1590 1009
1353 66
1054 370
526 169
1790 591
2287 2129
1959 855
2679 2364
903 654
256 101
752 595
1683 904
2494 485
236 64
2796 1904
2037 1038
2396 934
2898 ...

output:

result:

ok 5000 numbers