QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #312724 | #7977. 彩虹航线 | zhouhuanyi | 3 | 302ms | 58532kb | C++14 | 2.6kb | 2024-01-24 11:05:48 | 2024-01-24 11:05:49 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#define N 150
#define M 22500
#define K 1000000
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int n,m,k,nt[N+1],nt2[N+1],X[M+1],Y[M+1],cl[M+1],cls[M+1],c[M+1][N+1],snum[N+1][N+1],num[N+1][N+1],num2[N+1][N+1],tong[N+1],length;
vector<int>p[K+1];
vector<int>E[N+1];
vector<int>E2[N+1];
void adder(int x,int y)
{
int l1=0,l2=0,op=0;
for (int i=1;i<=k;++i)
{
if (!num[x][i]&&!num2[y][i])
{
num[x][i]=y,num2[y][i]=x;
return;
}
if (!num[x][i]) l1=i;
if (!num2[y][i]) l2=i;
}
length=0;
if (l1<l2) tong[++length]=x,tong[++length]=y;
else tong[++length]=y,tong[++length]=x;
while (1)
{
if ((!op)^(l1>l2))
{
if (num2[y][l1]) x=num2[y][l1],tong[++length]=x;
else break;
}
else
{
if (num[x][l2]) y=num[x][l2],tong[++length]=y;
else break;
}
op^=1;
}
for (int i=2;i+1<=length;++i)
{
if ((!(i&1))^(l1>l2)) num2[tong[i]][l1]=num[tong[i+1]][l1]=0;
else num[tong[i]][l2]=num2[tong[i+1]][l2]=0;
}
for (int i=1;i+1<=length;++i)
{
if ((i&1)^(l1>l2)) num[tong[i]][l1]=tong[i+1],num2[tong[i+1]][l1]=tong[i];
else num2[tong[i]][l2]=tong[i+1],num[tong[i+1]][l2]=tong[i];
}
return;
}
int main()
{
int d;
bool op;
n=read(),m=read(),k=read();
for (int i=1;i<=m;++i)
{
X[i]=read(),Y[i]=read(),snum[X[i]][Y[i]]=i,adder(X[i],Y[i]);
for (int j=1;j<=k;++j) c[i][j]=read();
}
for (int i=1;i<=n;++i)
for (int j=1;j<=k;++j)
if (num[i][j])
cl[snum[i][num[i][j]]]=j;
for (int i=1;i<=k;++i)
for (int j=1;j<=n;++j)
if (num[j][i])
{
d=snum[j][num[j][i]];
for (int t=1;t<=k;++t) p[c[d][t]].push_back(d);
}
for (int i=1;i<=K;++i)
{
for (int j=1;j<=n;++j) E[j].clear(),E2[j].clear();
for (int j=0;j<p[i].size();++j)
if (!cls[p[i][j]])
E[X[p[i][j]]].push_back(Y[p[i][j]]),E2[Y[p[i][j]]].push_back(X[p[i][j]]);
while (1)
{
op=0;
for (int j=1;j<=n;++j)
{
if (!E[j].empty()) nt[j]=E[j].back(),op=1;
else nt[j]=0;
}
if (!op) break;
for (int j=1;j<=n;++j)
{
nt2[j]=0;
for (int t=0;t<E2[j].size();++t)
if (nt[E2[j][t]]==j)
{
nt2[j]=E2[j][t];
break;
}
}
for (int j=1;j<=n;++j)
if (nt2[j])
cls[snum[nt2[j]][j]]=i,E[nt2[j]].clear(),E2[j].clear();
for (int j=1;j<=n;++j)
if (!E[j].empty())
E[j].pop_back();
}
}
for (int i=1;i<=m;++i) printf("%d ",cls[i]);
puts("");
return 0;
}
详细
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 225ms
memory: 28144kb
input:
150 150 1 144 5 1 141 54 1 26 120 1 148 68 1 136 62 1 114 1 1 33 136 1 85 100 1 97 124 1 84 66 1 107 81 1 82 135 1 112 44 1 20 89 1 50 32 1 52 94 1 89 88 1 3 57 1 130 23 1 140 150 1 96 37 1 122 38 1 41 63 1 99 85 1 13 95 1 142 47 1 95 4 1 69 17 1 27 119 1 73 93 1 108 43 1 54 18 1 37 76 1 67 114 1 40...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok construction is correct.
Test #2:
score: 0
Accepted
time: 230ms
memory: 29416kb
input:
150 150 1 117 132 96 147 4 114 67 57 60 62 94 20 48 117 68 31 144 27 19 44 121 3 51 92 83 52 67 26 125 56 8 124 75 125 31 52 79 8 21 132 14 136 77 111 45 134 136 145 129 73 85 122 92 143 59 76 36 60 127 115 102 126 133 10 106 32 93 35 106 75 47 102 45 140 41 44 108 146 25 98 106 140 116 76 143 3 87 ...
output:
96 114 60 20 68 27 121 92 67 56 75 52 21 136 45 145 85 143 36 115 133 32 106 102 41 146 106 76 87 90 116 15 147 51 35 85 15 83 43 105 89 12 89 140 103 114 135 78 93 80 87 93 19 7 125 132 96 96 99 48 1 63 3 6 146 116 48 9 126 6 106 64 74 84 16 23 119 51 7 83 96 56 94 97 27 15 51 106 95 32 70 103 75 8...
result:
ok construction is correct.
Test #3:
score: 0
Accepted
time: 234ms
memory: 27992kb
input:
150 10 1 35 145 1 145 88 2 130 14 1 111 142 1 138 99 1 76 73 1 101 79 1 147 137 2 65 64 1 108 8 2
output:
1 2 1 1 1 1 1 2 1 2
result:
ok construction is correct.
Subtask #2:
score: 2
Accepted
Test #4:
score: 2
Accepted
time: 224ms
memory: 48692kb
input:
75 5625 150 11 6 680849 150419 731361 419631 223710 806977 837589 529911 568337 456216 515190 302854 672904 388629 548276 803173 770491 610684 550790 786097 253610 446581 705772 610053 637171 567249 365794 571846 431219 213414 466432 53255 748825 765338 761154 556712 159152 463622 706471 49434 59624...
output:
980 3381 1885 123 19436 2560 2359 3518 22349 781 3686 5196 6995 58 34 631 7775 5611 9896 1481 11434 2253 2756 170 1112 7853 9236 20266 5409 1781 3095 1124 2145 201 8611 430 3048 1838 129 7881 9615 12237 335 425 9372 303 4913 1877 16645 6954 5793 1073 6631 8819 14 1400 11886 3472 2148 3635 2287 15866...
result:
ok construction is correct.
Test #5:
score: 0
Accepted
time: 120ms
memory: 35612kb
input:
75 5625 150 55 59 136 110 80 141 34 72 121 2 116 38 39 16 56 20 147 81 58 64 24 83 73 30 127 97 128 35 77 96 54 21 106 57 32 115 133 84 50 103 94 45 68 53 31 8 55 44 89 41 36 150 3 28 9 98 66 49 119 101 114 112 82 11 22 124 134 107 105 90 88 145 87 135 26 79 37 122 10 15 104 27 18 120 7 13 46 139 40...
output:
76 75 77 75 79 75 79 75 75 75 75 80 74 74 74 77 79 75 75 75 75 71 74 77 74 79 73 54 74 74 80 74 78 79 79 74 79 77 75 71 73 75 74 79 74 79 76 78 75 74 73 73 72 72 79 73 69 60 76 80 75 79 79 80 75 73 75 72 73 71 75 72 64 78 79 74 68 72 71 78 77 74 75 74 78 75 75 72 71 75 74 75 79 78 74 75 74 79 74 78 ...
result:
ok construction is correct.
Test #6:
score: 0
Accepted
time: 186ms
memory: 44016kb
input:
75 3750 150 1 29 15545 372923 77579 125076 509966 151564 332286 414939 296369 227609 9580 52174 99587 224186 2679 309545 38096 115252 281893 44718 259941 187595 500086 197842 267668 399469 254416 114691 268905 112134 257669 210411 135373 423915 537194 17707 204354 99757 234452 307155 82087 64190 309...
output:
1133 8931 6979 292 4622 3682 3085 1837 3717 806 1577 243 3800 1530 5699 5036 5663 1854 1290 447 377 7910 1190 5340 9940 4996 13835 5304 878 5407 8178 3666 2542 478 23 3939 1330 449 6141 312 4935 2216 2337 96 6700 807 1509 776 23474 11235 10940 9509 5258 10608 7340 556 3767 3414 1978 748 6728 4270 29...
result:
ok construction is correct.
Test #7:
score: 0
Accepted
time: 121ms
memory: 33456kb
input:
75 3750 150 43 71 86 127 132 6 139 123 83 37 85 103 52 102 4 148 111 34 110 66 42 130 150 149 53 45 137 129 2 5 87 79 146 47 9 98 96 54 17 126 81 115 7 105 117 119 101 144 74 23 44 19 84 97 50 13 22 94 78 63 134 40 142 76 109 95 12 138 112 72 136 24 77 31 32 118 124 135 68 104 16 1 93 106 128 51 20 ...
output:
22 49 51 58 44 41 52 40 47 52 53 58 48 58 36 54 49 54 62 54 43 44 53 38 43 55 59 49 52 45 52 34 47 44 63 45 48 54 51 50 51 52 48 54 50 42 49 48 42 43 47 44 29 47 55 52 52 49 57 30 51 46 37 43 53 43 42 57 51 50 36 43 53 54 53 47 55 49 48 46 49 45 50 56 49 43 53 42 47 40 31 49 47 47 48 55 48 36 53 53 ...
result:
ok construction is correct.
Subtask #3:
score: 0
Wrong Answer
Test #8:
score: 11
Accepted
time: 226ms
memory: 27788kb
input:
150 300 2 81 6 1 2 64 88 1 2 5 76 2 1 22 9 2 1 32 142 1 2 97 32 2 1 18 87 1 2 146 100 2 1 56 139 1 2 61 109 2 1 124 105 2 1 126 145 1 2 16 19 1 2 16 138 2 1 131 111 2 1 145 111 2 1 59 59 2 1 89 43 1 2 2 38 1 2 63 149 2 1 46 48 1 2 140 131 1 2 86 10 2 1 116 40 1 2 123 38 2 1 75 109 2 1 131 142 1 2 9 ...
output:
2 2 2 2 2 1 2 2 1 2 1 1 1 2 2 1 1 2 2 1 1 1 1 2 1 1 1 1 2 1 1 2 2 2 2 2 1 1 2 1 1 2 1 1 2 2 1 2 2 2 2 1 1 1 1 1 2 1 2 2 2 1 2 1 1 2 1 1 2 1 1 1 1 2 2 2 1 2 1 2 2 1 2 1 2 1 1 1 2 1 1 1 1 2 2 1 2 1 1 1 2 1 2 1 2 2 2 1 2 2 2 2 2 1 2 1 1 2 1 2 1 1 2 2 1 2 1 2 1 1 2 2 2 2 2 2 1 1 2 1 2 2 2 2 2 1 2 1 2 2 ...
result:
ok construction is correct.
Test #9:
score: -11
Wrong Answer
time: 235ms
memory: 28392kb
input:
150 300 2 60 122 3 1 114 17 2 1 21 19 3 1 134 75 3 1 64 81 2 1 52 33 1 3 45 27 1 2 148 91 2 1 110 100 1 2 100 74 2 3 53 130 3 2 59 19 3 1 149 108 3 1 19 92 1 3 85 66 3 2 80 89 3 2 16 4 2 3 39 90 2 3 53 102 3 1 20 21 3 1 21 112 1 3 76 98 1 2 7 130 3 1 140 129 2 3 139 100 3 1 127 77 1 3 136 113 3 2 54...
output:
1 1 3 1 2 3 1 1 2 2 2 1 3 1 2 2 2 2 1 1 1 1 1 3 1 1 3 1 2 3 1 2 0 2 2 3 1 2 1 2 2 1 3 2 2 1 2 1 3 3 1 1 1 1 1 2 1 2 2 1 2 1 1 3 1 2 2 3 3 2 2 3 1 2 2 1 1 1 1 3 2 1 2 2 2 1 3 3 1 2 2 3 2 1 1 3 2 1 3 3 1 3 1 1 1 1 1 2 2 2 2 3 2 3 2 1 3 2 2 2 2 2 3 3 1 3 3 3 2 2 1 1 3 1 2 2 3 3 1 2 3 1 1 1 2 1 1 2 3 1 ...
result:
wrong answer Integer 0 violates the range [1, 600]
Subtask #4:
score: 0
Wrong Answer
Test #18:
score: 0
Wrong Answer
time: 302ms
memory: 58532kb
input:
149 22201 150 106 24 20 90 56 109 85 33 76 25 97 77 134 75 15 24 88 16 93 126 43 94 116 120 28 130 21 140 70 111 71 32 29 41 132 39 84 62 27 92 55 117 129 125 127 104 74 114 14 145 36 121 22 69 68 133 59 65 58 148 131 40 54 118 110 3 61 105 4 112 142 122 73 37 1 113 45 87 57 89 103 98 100 63 146 106...
output:
84 134 0 121 143 149 149 0 0 147 149 149 149 0 0 149 0 0 149 150 56 149 0 0 149 0 0 0 0 150 148 0 149 0 148 0 149 0 0 149 149 149 148 148 149 149 149 148 149 149 149 147 0 149 148 0 149 0 148 149 143 149 0 148 149 149 149 148 147 0 148 148 148 149 146 0 133 148 147 147 149 148 149 149 147 0 146 150 ...
result:
wrong answer Integer 0 violates the range [1, 3330150]
Subtask #5:
score: 0
Wrong Answer
Test #23:
score: 21
Accepted
time: 291ms
memory: 58120kb
input:
150 22500 150 117 116 91 74 113 95 110 26 141 115 38 66 71 138 17 83 112 99 149 18 3 44 15 28 53 114 96 37 7 145 20 109 80 19 117 16 63 27 42 137 135 132 14 39 1 148 147 30 68 126 12 32 57 67 119 139 124 46 133 24 36 51 69 88 131 60 86 140 102 29 100 150 35 123 84 85 90 105 75 45 77 143 130 127 98 7...
output:
150 150 150 150 150 150 149 150 149 149 150 150 150 150 150 150 150 150 150 150 150 149 150 150 149 150 150 150 149 150 149 150 150 150 150 149 150 150 150 149 149 149 150 150 150 149 150 150 150 149 150 150 150 150 149 148 150 149 150 150 150 150 149 149 150 150 150 150 149 148 149 149 148 150 149 ...
result:
ok construction is correct.
Test #24:
score: -21
Wrong Answer
time: 286ms
memory: 58332kb
input:
150 22500 150 147 68 107 8 61 49 133 15 148 55 122 84 72 75 29 19 118 99 51 79 142 117 11 50 149 69 87 45 73 92 41 110 56 144 128 47 77 78 141 48 31 53 136 103 94 26 145 151 121 46 101 58 38 10 102 126 22 140 138 40 129 96 82 150 95 30 27 100 28 13 114 74 81 52 116 17 4 143 66 90 20 2 111 21 7 91 68...
output:
0 150 150 150 150 150 150 150 0 134 150 150 0 146 150 0 150 150 150 150 148 149 150 150 150 0 149 66 150 150 0 150 0 0 150 151 149 0 0 0 0 0 131 149 0 148 150 149 149 147 150 149 150 151 150 150 0 150 0 0 136 0 0 149 0 149 151 0 0 0 147 0 150 0 148 0 151 150 0 149 23 150 150 0 148 0 147 0 0 106 0 15...
result:
wrong answer Integer 0 violates the range [1, 3375000]
Subtask #6:
score: 0
Wrong Answer
Test #29:
score: 28
Accepted
time: 229ms
memory: 27804kb
input:
150 450 3 57 22 2 1 3 142 57 1 3 2 138 113 3 1 2 13 77 2 3 1 43 112 1 2 3 82 99 2 1 3 66 65 3 1 2 3 31 2 1 3 24 146 3 2 1 127 18 2 3 1 125 37 1 2 3 13 137 1 2 3 105 127 1 3 2 54 20 1 2 3 48 15 3 1 2 23 71 2 3 1 30 28 1 2 3 125 146 1 3 2 68 120 2 1 3 38 92 2 1 3 101 100 1 3 2 81 28 1 3 2 70 7 1 2 3 1...
output:
3 1 3 1 3 3 1 3 3 1 1 3 1 1 3 2 2 2 3 1 2 1 1 2 2 3 3 3 2 3 3 2 3 3 3 3 1 2 3 3 3 2 3 1 3 3 1 1 2 1 3 3 3 2 2 1 2 1 1 2 2 3 3 1 1 2 2 2 1 3 2 1 2 2 1 3 2 3 1 2 1 3 2 1 2 1 3 2 3 3 3 2 3 1 1 3 1 2 3 1 2 3 3 3 2 2 1 2 2 3 1 3 1 2 1 2 2 3 1 1 1 3 2 2 2 2 1 3 3 1 1 2 1 2 1 3 3 2 3 3 3 2 3 2 1 2 1 2 3 3 ...
result:
ok construction is correct.
Test #30:
score: 0
Accepted
time: 230ms
memory: 29352kb
input:
150 450 3 148 73 905 1007 1204 72 13 614 952 114 72 3 1026 931 764 33 21 1143 204 536 19 112 694 1261 734 104 68 1057 72 1249 83 66 311 147 656 141 5 1349 1317 700 12 113 331 375 1165 49 7 1114 1149 1224 79 41 531 46 712 128 20 630 1175 399 35 74 421 1148 608 57 124 840 108 1238 63 22 922 403 203 35...
output:
905 114 764 204 694 72 147 700 331 1114 46 399 421 108 203 5 223 132 98 676 134 203 42 31 341 976 822 798 64 94 212 266 374 384 52 708 990 76 249 492 130 313 529 89 46 681 15 460 911 833 194 395 104 617 308 122 50 405 38 776 49 25 41 1067 106 986 146 523 366 290 757 103 575 873 100 467 153 211 762 4...
result:
ok construction is correct.
Test #31:
score: -28
Wrong Answer
time: 233ms
memory: 28084kb
input:
150 450 3 111 66 3 4 1 62 51 3 2 4 117 58 3 4 1 54 105 1 3 4 40 108 3 1 4 104 112 2 4 1 131 73 4 3 1 109 30 1 4 3 36 130 3 4 2 40 70 2 3 1 24 112 3 1 4 44 119 4 1 2 39 91 1 4 3 28 118 1 2 3 8 117 2 4 1 110 109 3 1 4 99 20 4 1 2 131 49 4 1 2 130 114 1 4 3 133 57 3 1 2 41 125 1 3 4 21 65 1 2 3 144 143...
output:
3 2 3 1 4 1 3 3 3 1 3 0 3 3 1 3 1 1 3 1 3 3 4 2 1 4 4 2 4 1 2 2 1 3 1 2 2 2 4 4 3 4 2 1 3 2 1 3 1 2 2 2 2 4 3 4 2 2 2 2 1 2 3 4 3 2 4 0 4 1 1 3 4 1 3 3 1 1 1 2 4 3 2 3 3 2 1 2 4 1 2 2 2 3 1 4 2 2 4 3 4 2 4 1 0 1 4 2 2 2 1 4 3 1 2 2 2 3 3 1 4 1 2 2 2 0 2 4 4 4 1 1 2 2 0 4 3 3 3 3 2 2 1 1 4 4 0 2 3 0 ...
result:
wrong answer Integer 0 violates the range [1, 1350]