QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#367213	#7977. 彩虹航线	unputdownable	3	90ms	19596kb	C++17	2.1kb	2024-03-25 20:21:43	2024-03-25 20:21:44

Judging History

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

[2024-03-25 20:21:44]
评测

测评结果：3
用时：90ms
内存：19596kb

查看

[2024-03-25 20:21:43]
提交

answer

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
// #define int long long
#define i64 long long
#define pii pair <int, int> 
using namespace std;
inline int read(void) {
    int x=0,sgn=1; char ch=getchar();
    while(ch<48||57<ch) {if(ch==45)sgn=0;ch=getchar();}
    while(47<ch&&ch<58) {x=x*10+ch-48;   ch=getchar();}
    return sgn? x:-x;
}
void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
/*
    write((Ans%p+p)%p); pls
*/
int n,m,k,N;
int cnt[1000006],deg[302];
struct edge {
    int u,v;
    int col[154];
    inline void init() {
        ++deg[u];
        ++deg[v];
        for(int i=1; i<=k; ++i) ++cnt[col[i]];
    }
    inline int val1() { return deg[u]*deg[v]; }
} E[22504];
int p[22504],res[22504];
set <int> cols[302];
inline void clear() { for(int i=1; i<=N; ++i) cols[i].clear(); }
inline void attempt1() {
    for(int i=1; i<=m; ++i) sort(E[i].col+1,E[i].col+k+1,[&](int x,int y) { return cnt[x]<cnt[y]; });
    for(int i=1; i<=m; ++i) p[i]=i;
    sort(p+1,p+m+1,[&](int x,int y) {
        return E[x].val1()<E[y].val1();
    });
    for(int i=1; i<=m; ++i) {
        int x=p[i];
        int u=E[x].u,v=E[x].v,c=-1;
        for(int j=1; j<=k; ++j) {
            c=E[x].col[j];
            if(cols[u].count(c)||cols[v].count(c)) continue;
            break;
        }
        if(c==-1) return ; // failed
        cols[u].insert(c);
        cols[v].insert(c);
        res[x]=c;
    }
    for(int i=1; i<=m; ++i) write(res[i]),putchar(" \n"[i==m]);
    exit(0);
}
signed main() {
    // freopen("localinput","r",stdin);
    // freopen("localoutput","w",stdout);
    n=read(); m=read(); k=read(); N=n<<1;
    for(int i=1; i<=m; ++i) {
        E[i].u=read();
        E[i].v=read()+n;
        for(int u=1; u<=k; ++u) E[i].col[u]=read();
        E[i].init();
    }
    attempt1();
    cerr<<"err!"<<endl;
    // fprintf(stderr,"%.4lf\n",1.0*clock()/CLOCKS_PER_SEC);
    return 0;
}

源文件, 语言: C++17

詳細信息

Subtask #1:

score: 1

Accepted

Test #1:

score: 1

Accepted

time: 1ms

memory: 3680kb

input:

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

memory: 3776kb

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

memory: 3752kb

input:

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

memory: 10936kb

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:

385267 398795 662181 49603 743426 153192 64916 54871 535472 660899 183569 736519 647253 293004 370201 819882 534424 75157 108101 719297 77581 712598 712653 692113 35826 390133 412381 141307 684474 88556 137721 384790 293681 259705 743293 76755 308150 776558 298616 57259 348481 350516 396451 311574 7...

result:

ok construction is correct.

Test #5:

score: 0

Accepted

time: 15ms

memory: 7572kb

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:

74 146 74 128 114 7 150 102 103 145 57 14 98 73 15 32 119 73 89 143 87 5 72 4 35 6 33 21 45 138 34 8 7 112 121 55 83 30 19 122 65 12 120 69 120 114 90 19 72 113 7 12 112 146 5 81 78 58 81 93 79 80 132 3 29 139 127 132 14 23 122 82 10 126 96 79 131 77 33 128 105 13 31 51 124 90 29 147 39 85 16 99 15 ...

result:

ok construction is correct.

Test #6:

score: 0

Accepted

time: 21ms

memory: 8568kb

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:

65634 433835 210832 162172 414826 369274 462224 488801 101156 473411 129681 173040 407597 555100 508647 491772 88036 462849 541952 511200 417614 175866 420327 448212 49047 174111 121967 549618 84415 386314 542399 469888 170214 76873 438176 10826 53644 161126 216349 310157 375075 200841 96721 469750 ...

result:

ok construction is correct.

Test #7:

score: 0

Accepted

time: 6ms

memory: 6364kb

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:

73 2 14 143 61 139 116 129 111 75 35 35 65 109 132 115 65 45 91 83 17 85 42 46 108 82 75 140 98 23 25 121 61 78 65 100 130 47 4 103 107 55 54 105 102 12 52 127 24 13 40 63 102 49 53 84 26 92 21 21 78 107 93 141 65 22 112 130 51 71 136 102 2 33 77 94 90 52 6 112 88 54 27 146 104 52 64 6 89 95 27 137 ...

result:

ok construction is correct.

Subtask #3:

score: 0

Wrong Answer

Test #8:

score: 0

Wrong Answer

time: 1ms

memory: 3844kb

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

result:

wrong answer not a proper coloring.

Subtask #4:

score: 0

Wrong Answer

Test #18:

score: 0

Wrong Answer

time: 82ms

memory: 19328kb

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:

65 22 26 12 3 18 111 111 33 18 104 26 7 144 88 26 125 86 124 26 20 103 135 59 35 28 6 48 141 60 115 57 128 89 69 103 50 150 18 112 136 20 61 107 62 127 53 17 82 11 45 49 36 2 20 47 101 3 141 66 108 143 96 15 87 82 82 122 123 106 43 45 143 62 47 25 76 87 101 137 120 4 105 24 70 71 149 55 107 75 80 47...

result:

wrong answer not a proper coloring.

Subtask #5:

score: 0

Wrong Answer

Test #23:

score: 0

Wrong Answer

time: 90ms

memory: 19596kb

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:

22 49 140 81 36 67 86 75 3 112 67 76 88 131 46 91 87 84 53 100 115 138 3 145 69 38 132 121 56 10 26 13 56 64 65 97 32 114 77 33 83 118 6 68 85 1 107 62 83 92 81 39 29 36 95 95 140 25 75 71 88 35 40 106 106 42 66 25 117 127 113 120 47 18 89 122 126 41 38 46 89 122 116 96 9 82 26 96 135 98 13 17 95 15...

result:

wrong answer not a proper coloring.

Subtask #6:

score: 0

Wrong Answer

Test #29:

score: 0

Wrong Answer

time: 0ms

memory: 3908kb

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 2 1 2 2 2 3 2 2 2 3 3 2 2 1 1 3 1 3 1 1 1 2 1 2 1 3 1 3 1 2 1 3 2 1 3 3 3 2 1 3 2 3 2 3 3 3 1 2 3 2 3 3 3 2 1 1 2 2 2 2 2 2 1 1 3 2 1 3 3 1 1 3 3 1 3 1 3 3 3 2 2 2 1 2 3 2 3 2 2 2 3 2 1 3 1 3 1 1 2 1 1 3 3 1 1 2 1 2 3 3 2 1 3 3 2 1 1 1 3 2 2 2 2 3 3 1 1 2 3 3 1 3 2 1 1 3 2 3 1 1 1 3 3 3 1 3 3 1 1 ...

result:

wrong answer not a proper coloring.