QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#118644	#4303. New Level	Star32	WA	131ms	26456kb	C++14	1.2kb	2023-07-03 19:57:46	2023-07-03 19:57:47

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-07-03 19:57:47]
评测

测评结果：WA
用时：131ms
内存：26456kb

查看

[2023-07-03 19:57:46]
提交

answer

#include <bits/stdc++.h>
using namespace std;
int n,m,k,col[500005],dis[500005],inf=0x3f3f3f3f,rp;
struct node{
	int id,dis;
	bool operator<(node b)const{
		return dis>b.dis;
	}
};
int cnt,lst[500005];
struct edge{
	int f,t,val,lst;
	edge(int f=0,int t=0,int val=0,int lst=0):
		f(f),t(t),val(val),lst(lst){}
}e[1000005];
void add(int u,int v,int w=0){
	e[++cnt]=edge(u,v,w,lst[u]);lst[u]=cnt;
}
bool vis[500005];
void dij(){
	memset(dis,inf,sizeof(dis));
	dis[1]=0;
	priority_queue<node> q;q.push({1,0});
	while(!q.empty()){
		int u=q.top().id;q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=lst[u];i;i=e[i].lst){
			int v=e[i].t;
			if(dis[v]>dis[u]+e[i].val){
				dis[v]=dis[u]+e[i].val;
				q.push({v,dis[v]});
			}
		}
	}
}
signed main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)scanf("%d",&col[i]),col[i]--;
	for(int i=1;i<=m;i++){
		int u,v;scanf("%d%d",&u,&v);
		int d=(col[v]-1+k+k-col[u])%k;
		if(col[v]==(col[u]+1)%k||col[u]==(col[v]+1)%k){
			add(u,v,0),add(v,u,0);
			continue;
		}
		add(u,v,d);
		add(v,u,k-d);
	}
	dij();
	for(int i=1;i<=n;i++)col[i]=(col[i]+inf-dis[i])%k;
	for(int i=1;i<=n;i++)printf("%d ",col[i]+1);
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 22624kb

input:

output:

4 1 2 3

result:

ok n=4, m=4, k=4

Test #2:

score: 0

Accepted

time: 1ms

memory: 23340kb

input:

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

output:

3 2 3 3 1 2 3 1 1 2

result:

ok n=10, m=9, k=3

Test #3:

score: 0

Accepted

time: 1ms

memory: 22596kb

input:

239 238 10
6 1 2 10 9 1 8 10 1 10 6 4 5 2 7 8 4 9 7 5 1 3 2 8 1 7 3 4 6 4 2 6 3 10 3 10 5 1 8 8 1 1 2 3 5 5 5 9 3 8 3 4 7 10 7 5 7 8 2 6 8 10 3 3 2 1 7 5 1 4 4 1 9 9 4 2 10 1 6 10 5 3 8 4 4 10 4 4 2 9 9 6 6 8 2 3 2 4 8 5 10 10 3 3 5 1 4 8 4 2 3 6 10 4 10 2 8 2 2 5 7 5 3 3 8 1 7 10 2 8 2 6 3 10 6 5 9...

output:

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

result:

ok n=239, m=238, k=10

Test #4:

score: 0

Accepted

time: 1ms

memory: 23548kb

input:

2392 2391 100
89 13 96 29 35 81 10 62 30 4 46 56 15 37 61 8 45 47 5 29 23 64 98 50 18 34 28 24 20 24 10 43 34 28 64 100 61 22 68 37 61 49 37 74 64 53 1 84 54 30 46 25 21 31 96 49 74 19 4 10 29 72 27 48 28 99 74 8 32 89 46 68 73 87 41 72 25 2 27 66 77 90 24 78 65 34 67 25 11 9 16 17 87 2 56 58 48 56 ...

output:

56 55 54 54 53 54 53 52 53 54 53 52 51 53 50 51 52 51 52 51 55 52 55 51 54 51 53 51 54 51 53 50 52 53 54 51 51 49 49 50 52 50 50 53 51 48 51 53 53 50 53 51 55 52 52 53 49 51 52 49 48 50 50 51 49 50 48 51 53 51 50 49 52 47 50 52 48 52 49 47 52 47 49 52 51 47 51 52 54 52 52 55 49 50 48 50 52 55 51 53 ...

result:

ok n=2392, m=2391, k=100

Test #5:

score: 0

Accepted

time: 1ms

memory: 22668kb

input:

output:

1 3 1 2

result:

ok n=4, m=3, k=3

Test #6:

score: 0

Accepted

time: 1ms

memory: 22912kb

input:

5000 4999 215
75 104 70 136 199 28 108 67 92 90 200 35 184 21 81 200 48 193 172 143 109 43 89 94 195 149 176 198 96 101 199 207 112 29 7 123 59 3 14 38 99 152 188 15 188 179 47 190 199 117 3 63 187 77 14 166 41 8 7 209 211 95 6 80 174 135 211 95 211 189 180 118 210 20 111 24 192 67 129 116 182 17 17...

output:

147 146 146 145 144 145 143 145 143 144 142 146 145 145 146 144 143 145 142 141 140 142 144 144 142 142 143 142 141 141 144 139 145 140 145 143 143 142 143 146 144 143 140 146 140 143 138 145 143 145 144 144 145 140 146 145 144 143 144 139 142 145 139 143 142 137 144 144 143 143 144 140 144 139 144 ...

result:

ok n=5000, m=4999, k=215

Test #7:

score: 0

Accepted

time: 1ms

memory: 23196kb

input:

5000 4999 215
155 162 166 204 39 176 58 184 65 113 129 76 118 27 143 103 22 1 209 135 32 117 55 152 197 66 199 5 186 166 53 101 34 91 148 2 70 51 202 80 1 41 31 143 44 102 145 13 90 100 163 185 211 77 45 48 26 123 4 104 20 168 154 142 90 153 149 163 38 172 29 133 62 189 107 89 37 210 57 24 25 55 123...

output:

12 11 10 9 8 7 6 5 4 3 2 1 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 188 187 186 185 184 183 182 181 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154 153 152 151 150 149 148 1...

result:

ok n=5000, m=4999, k=215

Test #8:

score: 0

Accepted

time: 28ms

memory: 22704kb

input:

100000 99999 215
144 87 149 51 25 51 108 78 135 17 73 188 186 148 9 184 206 1 35 53 29 31 200 78 63 136 158 54 153 103 71 83 60 94 89 7 215 85 150 179 210 130 161 112 93 213 106 189 162 43 173 141 185 192 160 210 196 197 185 33 136 85 103 150 197 140 202 45 51 133 177 16 66 106 70 140 35 66 14 112 1...

output:

1 215 214 214 213 215 214 215 213 212 214 212 212 214 211 214 213 215 212 212 211 214 211 213 212 212 211 212 213 214 210 209 212 211 210 213 214 211 208 213 213 213 212 213 212 213 214 211 213 211 211 209 210 213 213 211 208 212 210 210 212 214 208 212 211 211 212 210 215 213 213 210 214 211 212 21...

result:

ok n=100000, m=99999, k=215

Test #9:

score: 0

Accepted

time: 30ms

memory: 22136kb

input:

100000 99999 215
8 183 153 16 17 143 160 152 91 68 8 161 194 91 107 15 206 155 125 10 109 22 77 17 151 148 175 139 182 167 153 115 16 113 58 182 191 203 215 106 34 159 17 182 139 44 30 129 105 134 57 157 32 56 214 5 62 180 175 61 120 15 214 97 103 24 209 194 127 87 204 89 156 2 36 74 114 163 206 97 ...

output:

80 79 78 77 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200...

result:

ok n=100000, m=99999, k=215

Test #10:

score: 0

Accepted

time: 77ms

memory: 25132kb

input:

239239 239238 239
146 41 60 184 200 183 12 18 119 159 195 222 203 34 50 160 207 170 130 87 232 87 92 221 84 33 38 237 187 102 50 204 3 135 227 23 110 116 215 28 27 238 239 91 153 214 233 193 77 167 203 167 83 200 214 234 68 188 232 197 67 17 210 199 17 222 103 213 99 212 159 76 134 182 89 134 44 92 ...

output:

142 141 141 140 139 140 141 140 140 139 140 140 139 139 139 139 138 137 140 138 138 138 140 138 136 137 139 139 138 138 136 139 138 140 139 139 138 137 136 140 139 135 137 135 139 135 138 138 138 138 137 141 137 138 139 136 139 138 136 140 139 138 140 139 138 138 138 137 137 136 139 137 136 137 137 ...

result:

ok n=239239, m=239238, k=239

Test #11:

score: 0

Accepted

time: 21ms

memory: 22884kb

input:

73223 73222 456
176 375 93 323 28 186 232 176 6 374 42 15 169 308 221 137 388 221 345 86 170 251 432 288 394 21 122 351 430 78 216 133 119 278 100 163 46 278 294 234 68 239 64 202 41 194 410 253 352 153 333 363 120 379 235 286 412 299 20 71 139 369 306 390 327 78 165 245 313 275 6 140 274 417 335 24...

output:

23 22 22 21 20 19 21 21 22 22 19 18 21 22 21 18 21 20 17 18 19 21 18 18 21 21 21 20 18 21 20 16 18 17 17 21 18 20 20 18 19 20 17 21 17 21 19 20 19 16 20 17 22 16 20 20 19 18 20 19 16 18 19 19 17 15 20 21 16 17 19 15 17 17 19 15 15 19 17 19 20 20 20 17 14 17 18 19 17 19 15 20 15 16 20 20 14 16 18 20 ...

result:

ok n=73223, m=73222, k=456

Test #12:

score: 0

Accepted

time: 131ms

memory: 25608kb

input:

500000 499999 120
120 109 52 88 118 102 96 49 54 40 65 119 104 14 83 86 70 71 108 13 89 86 79 93 2 3 84 120 10 22 116 111 41 2 25 18 65 70 99 99 107 21 75 98 24 95 106 40 40 77 26 103 53 63 35 120 80 56 38 35 82 24 108 26 35 88 47 53 29 8 15 53 89 67 109 69 64 9 51 3 2 99 48 11 82 90 47 91 47 31 9 7...

output:

87 86 85 86 86 85 84 83 84 84 85 84 83 83 84 85 85 85 82 83 83 82 84 84 84 85 81 80 85 84 82 83 84 86 83 83 83 83 81 79 82 84 83 82 82 81 80 84 85 85 83 82 83 81 84 85 82 82 81 82 81 84 82 83 83 80 81 85 81 81 85 82 84 84 86 83 82 85 81 81 84 83 81 82 82 83 82 80 78 84 81 83 80 84 80 83 81 81 81 82 ...

result:

ok n=500000, m=499999, k=120

Test #13:

score: 0

Accepted

time: 4ms

memory: 23080kb

input:

output:

2 1 1

result:

ok n=3, m=2, k=2

Test #14:

score: 0

Accepted

time: 1ms

memory: 22824kb

input:

output:

2 1 3 1

result:

ok n=4, m=3, k=3

Test #15:

score: 0

Accepted

time: 1ms

memory: 23684kb

input:

2 1 2
1 2
2 1

output:

2 1

result:

ok n=2, m=1, k=2

Test #16:

score: 0

Accepted

time: 0ms

memory: 22680kb

input:

10 45 10
1 2 3 4 5 6 7 8 9 10
1 3
1 4
1 5
1 9
2 1
2 4
2 5
2 8
2 9
2 10
3 2
3 7
3 8
3 10
4 3
4 6
4 7
4 10
5 3
5 4
5 8
6 1
6 2
6 3
6 5
6 8
7 1
7 2
7 5
7 6
7 9
7 10
8 1
8 4
8 7
9 3
9 4
9 5
9 6
9 8
10 1
10 5
10 6
10 8
10 9

output:

8 9 10 1 2 3 4 5 6 7

result:

ok n=10, m=45, k=10

Test #17:

score: 0

Accepted

time: 70ms

memory: 25316kb

input:

1000 499500 1000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...

output:

568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 ...

result:

ok n=1000, m=499500, k=1000

Test #18:

score: 0

Accepted

time: 1ms

memory: 22916kb

input:

239 28441 239
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

236 237 238 239 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...

result:

ok n=239, m=28441, k=239

Test #19:

score: 0

Accepted

time: 1ms

memory: 22684kb

input:

output:

4 1 2 3

result:

ok n=4, m=6, k=4

Test #20:

score: 0

Accepted

time: 72ms

memory: 26456kb

input:

999 498501 999
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:

739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 ...

result:

ok n=999, m=498501, k=999

Test #21:

score: 0

Accepted

time: 1ms

memory: 24824kb

input:

30 435 30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
1 3
1 4
1 6
1 7
1 8
1 9
1 10
1 13
1 17
1 20
1 21
1 25
1 26
1 27
2 1
2 4
2 5
2 6
2 8
2 11
2 14
2 15
2 16
2 17
2 18
2 19
2 21
2 23
2 26
2 27
2 29
3 2
3 6
3 7
3 12
3 13
3 15
3 16
3 17
3 20
3 21
3 27
3 29
3 30
4 3...

output:

28 29 30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

result:

ok n=30, m=435, k=30

Test #22:

score: 0

Accepted

time: 2ms

memory: 22468kb

input:

37 666 37
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
1 3
1 9
1 10
1 11
1 14
1 17
1 18
1 19
1 23
1 25
1 26
1 28
1 29
1 30
1 31
1 34
1 35
1 37
2 1
2 5
2 7
2 8
2 9
2 11
2 12
2 14
2 15
2 18
2 19
2 20
2 21
2 23
2 24
2 25
2 26
2 30
2 33
2 35
2 37
...

output:

36 37 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

result:

ok n=37, m=666, k=37

Test #23:

score: 0

Accepted

time: 12ms

memory: 21936kb

input:

500 124750 500
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:

68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 ...

result:

ok n=500, m=124750, k=500

Test #24:

score: 0

Accepted

time: 73ms

memory: 25272kb

input:

988 487578 988
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:

532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 ...

result:

ok n=988, m=487578, k=988

Test #25:

score: 0

Accepted

time: 51ms

memory: 25196kb

input:

932 433846 932
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...

output:

540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 ...

result:

ok n=932, m=433846, k=932

Test #26:

score: 0

Accepted

time: 4ms

memory: 24632kb

input:

1 0 1
1

output:

result:

ok n=1, m=0, k=1

Test #27:

score: 0

Accepted

time: 1ms

memory: 23820kb

input:

2 1 2
1 2
2 1

output:

2 1

result:

ok n=2, m=1, k=2

Test #28:

score: 0

Accepted

time: 0ms

memory: 23716kb

input:

2 1 2
1 2
2 1

output:

2 1

result:

ok n=2, m=1, k=2

Test #29:

score: 0

Accepted

time: 4ms

memory: 23952kb

input:

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

output:

4 1 2 1 4 3 2 1 2 1

result:

ok n=10, m=9, k=4

Test #30:

score: -100

Wrong Answer

time: 6ms

memory: 21536kb

input:

1000 10000 100
87 95 7 96 16 76 19 68 100 93 31 85 63 77 82 42 85 33 98 25 89 25 99 92 24 87 80 86 77 67 3 5 19 90 33 86 89 38 26 14 19 40 28 14 99 31 60 87 19 71 10 14 37 66 68 64 89 4 91 37 28 19 76 72 91 70 31 37 28 42 26 24 38 51 63 6 22 22 44 1 55 40 36 69 82 61 5 91 32 63 60 73 99 31 54 2 66 1...

output:

54 53 54 53 54 71 55 70 79 53 57 72 60 71 69 60 70 59 53 53 77 56 79 52 55 78 74 72 72 67 50 51 54 80 58 71 79 58 57 51 54 61 58 53 80 57 65 74 56 68 78 54 61 64 66 60 74 78 77 58 57 56 72 71 79 67 56 60 56 61 54 51 59 57 64 52 57 79 59 77 64 58 60 71 73 66 54 74 58 69 66 74 79 56 64 51 67 54 52 75 ...

result:

wrong answer Vertices 3 and 1 have the same color