CSES - HIIT Open 2025

Submission details
Task:	Coloring
Sender:	Makkara
Submission time:	2025-11-08 14:37:10 +0200
Language:	C++ (C++17)
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.00 s	details
#2	ACCEPTED	0.26 s	details
#3	ACCEPTED	0.27 s	details
#4	ACCEPTED	0.30 s	details
#5	ACCEPTED	0.00 s	details
#6	ACCEPTED	0.00 s	details
#7	ACCEPTED	0.00 s	details
#8	ACCEPTED	0.00 s	details
#9	ACCEPTED	0.01 s	details
#10	ACCEPTED	0.02 s	details
#11	ACCEPTED	0.24 s	details
#12	ACCEPTED	0.51 s	details
#13	ACCEPTED	0.51 s	details
#14	ACCEPTED	0.52 s	details
#15	ACCEPTED	0.00 s	details
#16	ACCEPTED	0.22 s	details
#17	ACCEPTED	0.42 s	details
#18	ACCEPTED	0.00 s	details
#19	ACCEPTED	0.01 s	details
#20	ACCEPTED	0.29 s	details
#21	ACCEPTED	0.00 s	details
#22	ACCEPTED	0.00 s	details
#23	ACCEPTED	0.30 s	details
#24	ACCEPTED	0.01 s	details
#25	ACCEPTED	0.04 s	details
#26	ACCEPTED	0.14 s	details
#27	ACCEPTED	0.27 s	details

Code

#include <bits/stdc++.h>
using namespace std;

struct Vertex {
  vector<int> adj2;
  unordered_set<int> adj;
  int color;
  bool badcolor[6];
  bool seen;
};

int main() {
  int n, m;
  cin >> n >> m;
  Vertex E[n];
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    E[u - 1].adj.insert(v - 1);
    E[v - 1].adj.insert(u - 1);
    E[u - 1].adj2.push_back(v - 1);
    E[v - 1].adj2.push_back(u - 1);
  }
  priority_queue<pair<int, int>> heap;
  for (int i = 0; i < n; ++i) {
    E[i].color = -1;
    heap.push({-E[i].adj2.size(), i});
    for (int j = 0; j < 6; ++j)
      E[i].badcolor[j] = false;
    E[i].seen = false;
  }
  int cnt = 0;
  vector <int> order;
  while (cnt < n) {
    int v = heap.top().second;
    heap.pop();
    if (E[v].seen) continue;
    E[v].seen = true;
    cnt++;
    order.push_back(v);
    for (int u : E[v].adj) {
      E[u].adj.erase(E[u].adj.find(v));
      heap.push({-E[u].adj.size(), u});
    }
  }
    
  for (int j = n - 1; j >= 0; --j) {
    int v = order[j];
    for (int i = 0; i < 6; ++i) {
      if (!E[v].badcolor[i]) {
        E[v].color = i;
        for (int u : E[v].adj2) {
          E[u].badcolor[i] = true;
        }
        break;
      }
    }
  }
  
  for (int i = 0; i < n; ++i) {
    cout << E[i].color + 1 << " "[i == n-1];
  }
  cout << endl;
  
  return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
`5 6 1 2 2 3 3 1 2 4 ...` view save

correct output
`2 3 1 2 1` view save

user output
`1 2 3 1 3` view save

Test 2

Verdict: ACCEPTED

input
`100000 199998 1 2 2 3 3 4 4 5 ...` view save

correct output
`4 3 2 3 2 3 2 3 2 3 2 3 2 3 2 ...` view save

user output
`1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...` view save

Test 3

Verdict: ACCEPTED

input
`81251 200000 1 2 2 3 3 4 4 5 ...` view save

correct output
`3 2 1 4 1 4 1 3 2 4 3 2 1 5 3 ...` view save

user output
`1 2 3 4 3 4 3 1 2 1 2 4 3 1 2 ...` view save

Test 4

Verdict: ACCEPTED

input
`81251 200000 1 6251 6251 12501 12501 18751 18751 25001 ...` view save

correct output
`3 5 3 5 3 5 3 5 3 5 3 5 3 5 3 ...` view save

user output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

Test 5

Verdict: ACCEPTED

input
`2 1 1 2` view save

correct output
`2 1` view save

user output
`1 2` view save

Test 6

Verdict: ACCEPTED

input
`5 7 3 1 3 4 2 4 2 5 ...` view save

correct output
`1 3 3 2 1` view save

user output
`2 1 1 2 3` view save

Test 7

Verdict: ACCEPTED

input
`9 10 4 6 5 8 9 6 5 4 ...` view save

correct output
`3 2 1 1 3 2 1 1 1` view save

user output
`2 1 1 1 2 3 1 1 2` view save

Test 8

Verdict: ACCEPTED

input
`65 100 34 52 42 65 48 6 62 63 ...` view save

correct output
`2 2 3 2 1 1 4 1 5 3 3 4 3 1 1 ...` view save

user output
`2 1 2 1 2 2 3 1 2 1 1 1 1 1 1 ...` view save

Test 9

Verdict: ACCEPTED

input
`661 1000 102 270 29 1 235 291 1 28 ...` view save

correct output
`2 1 1 1 2 1 1 2 1 2 2 2 3 2 3 ...` view save

user output
`1 1 2 2 2 1 1 3 1 2 2 1 2 2 1 ...` view save

Test 10

Verdict: ACCEPTED

input
`6658 10000 6255 6351 6240 811 5121 5120 562 563 ...` view save

correct output
`3 3 1 1 2 2 1 2 3 1 3 3 2 1 2 ...` view save

user output
`1 2 1 1 1 2 1 3 1 2 2 3 2 1 1 ...` view save

Test 11

Verdict: ACCEPTED

input
`66713 100002 17616 53797 36477 36478 9289 9288 30331 12908 ...` view save

correct output
`2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 ...` view save

user output
`2 3 2 1 2 1 1 1 1 1 3 2 2 2 2 ...` view save

Test 12

Verdict: ACCEPTED

input
`133153 199900 84918 102523 65880 121666 112752 112751 119806 92639 ...` view save

correct output
`1 3 1 1 1 2 1 2 1 2 1 2 1 2 1 ...` view save

user output
`3 2 1 1 1 2 1 3 2 1 3 3 1 1 2 ...` view save

Test 13

Verdict: ACCEPTED

input
`132902 199904 38449 38448 103004 31700 24769 12112 102436 54041 ...` view save

correct output
`1 1 2 1 1 3 1 2 1 1 1 1 1 1 1 ...` view save

user output
`2 2 2 3 1 2 1 2 2 2 2 2 1 2 1 ...` view save

Test 14

Verdict: ACCEPTED

input
`133659 199900 106579 112407 107263 107093 11493 44214 15803 15804 ...` view save

correct output
`2 2 1 1 1 2 1 1 1 1 2 1 1 2 3 ...` view save

user output
`1 1 3 2 1 2 2 1 1 1 1 1 3 2 3 ...` view save

Test 15

Verdict: ACCEPTED

input
`36 85 28 29 8 9 36 30 14 8 ...` view save

correct output
`1 3 2 1 3 2 3 2 1 3 2 1 2 1 3 ...` view save

user output
`1 2 3 1 2 3 2 3 1 2 3 1 3 1 2 ...` view save

Test 16

Verdict: ACCEPTED

input
`40000 119201 16810 16610 34321 34120 38157 37956 24084 23883 ...` view save

correct output
`3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 ...` view save

user output
`1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...` view save

Test 17

Verdict: ACCEPTED

input
`80000 199993 29955 9954 47408 27408 51231 51232 37204 37205 ...` view save

correct output
`1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...` view save

user output
`1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...` view save

Test 18

Verdict: ACCEPTED

input
`15 35 3 2 3 4 4 2 5 4 ...` view save

correct output
`2 1 3 2 4 5 2 3 4 3 2 4 3 2 1` view save

user output
`2 1 2 3 4 3 4 2 4 2 3 2 3 4 1` view save

Test 19

Verdict: ACCEPTED

input
`143 352 3 2 3 4 4 2 5 4 ...` view save

correct output
`1 3 4 1 5 2 1 4 5 1 2 4 3 2 1 ...` view save

user output
`2 1 2 3 4 3 4 2 4 2 3 2 3 4 1 ...` view save

Test 20

Verdict: ACCEPTED

input
`81256 198855 3 2 3 4 4 2 5 4 ...` view save

correct output
`1 3 4 1 5 2 1 4 5 1 2 4 3 2 1 ...` view save

user output
`2 1 2 3 4 3 4 2 4 2 3 2 3 4 1 ...` view save

Test 21

Verdict: ACCEPTED

input
`15 33 3 2 3 4 4 2 5 4 ...` view save

correct output
`1 1 3 2 4 3 2 1 3 5 4 3 2 1 2` view save

user output
`1 1 4 2 3 4 2 3 1 2 3 1 3 4 2` view save

Test 22

Verdict: ACCEPTED

input
`137 326 3 2 3 4 4 2 5 4 ...` view save

correct output
`1 1 3 2 4 3 2 1 3 5 4 3 2 1 2 ...` view save

user output
`2 1 4 2 3 4 2 3 1 2 3 1 3 4 3 ...` view save

Test 23

Verdict: ACCEPTED

input
`82312 198211 3 2 3 4 4 2 5 4 ...` view save

correct output
`1 1 3 2 4 3 2 1 3 5 4 3 2 1 2 ...` view save

user output
`2 1 4 2 3 4 2 3 1 2 3 1 3 4 3 ...` view save

Test 24

Verdict: ACCEPTED

input
`512 1025 2 13 13 3 2 14 14 3 ...` view save

correct output
`2 1 2 5 1 3 4 2 1 2 1 4 3 3 3 ...` view save

user output
`1 3 1 2 3 4 3 1 2 1 2 3 2 2 2 ...` view save

Test 25

Verdict: ACCEPTED

input
`15342 30761 2 13 13 3 2 14 14 3 ...` view save

correct output
`1 3 2 5 1 3 4 2 1 2 1 4 1 1 1 ...` view save

user output
`1 3 1 2 3 4 3 1 2 1 2 3 2 2 2 ...` view save

Test 26

Verdict: ACCEPTED

input
`51148 102547 2 13 13 3 2 14 14 3 ...` view save

correct output
`1 3 2 5 1 3 4 2 1 2 1 4 1 1 1 ...` view save

user output
`1 3 1 2 3 4 3 1 2 1 2 3 2 2 2 ...` view save

Test 27

Verdict: ACCEPTED

input
`99735 199964 2 13 13 3 2 14 14 3 ...` view save

correct output
`1 3 2 5 1 3 4 2 1 2 1 4 1 1 1 ...` view save

user output
`1 3 1 2 3 4 3 1 2 1 2 3 2 2 2 ...` view save

HIIT Open 2025

Coloring

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Tasks

Submissions (Makkara)