Submission #1246765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246765		vht2025	Fliper (COCI22_fliper)	C++20	0 / 110	1286 ms	56984 KiB

Main

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

using namespace std;

struct Obstacle {
    int id;
    int x, y;
    char type;
    vector<int> adj; // Lưu các đỉnh kề trong đồ thị chu trình
};

map<int, int> obs_at_pos[4]; // UP, DOWN, LEFT, RIGHT
vector<int> bipartite_color;
vector<bool> visited;
vector<int> final_colors;

// DFS để tìm chu trình và tô màu 2 phía
bool find_and_color_cycles(int u, int c, const vector<Obstacle>& obstacles) {
    visited[u] = true;
    bipartite_color[u] = c;

    int current = u;
    int len = 0;
    do {
        visited[current] = true;
        len++;
        if(obstacles[current].adj.empty()) { // Path, not cycle
            len = 0;
            break;
        }
        current = obstacles[current].adj[0]; // Chỉ có 1 đường ra
    } while (current != u && !visited[current]);

    if (current == u) { // Found a cycle
        if (len % 8 != 0) return false;
    }
    
    // Tô màu 2 phía cho toàn bộ thành phần liên thông
    vector<int> q;
    q.push_back(u);
    visited.assign(obstacles.size(), false);
    visited[u] = true;

    int head = 0;
    while(head < q.size()){
        int curr = q[head++];
        for(int neighbor : obstacles[curr].adj){
            if(!visited[neighbor]){
                visited[neighbor] = true;
                bipartite_color[neighbor] = 1 - bipartite_color[curr];
                q.push_back(neighbor);
            }
        }
    }

    return true;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<Obstacle> obstacles(n);
    map<int, vector<pair<int, int>>> group_by_x, group_by_y;

    for (int i = 0; i < n; ++i) {
        obstacles[i].id = i;
        cin >> obstacles[i].x >> obstacles[i].y >> obstacles[i].type;
        group_by_x[obstacles[i].x].push_back({obstacles[i].y, i});
        group_by_y[obstacles[i].y].push_back({obstacles[i].x, i});
    }

    for (auto const& [x_val, vec] : group_by_x) {
        sort(group_by_x[x_val].begin(), group_by_x[x_val].end());
    }
    for (auto const& [y_val, vec] : group_by_y) {
        sort(group_by_y[y_val].begin(), group_by_y[y_val].end());
    }

    // Xây dựng đồ thị
    for (int i = 0; i < n; ++i) {
        int x = obstacles[i].x;
        int y = obstacles[i].y;
        
        // Tìm hàng xóm trên/dưới
        auto& col = group_by_x[x];
        auto it = lower_bound(col.begin(), col.end(), make_pair(y, i));
        int my_idx_in_col = distance(col.begin(), it);
        
        int up_neighbor = (my_idx_in_col + 1 < col.size()) ? col[my_idx_in_col + 1].second : -1;
        int down_neighbor = (my_idx_in_col > 0) ? col[my_idx_in_col - 1].second : -1;

        // Tìm hàng xóm trái/phải
        auto& row = group_by_y[y];
        it = lower_bound(row.begin(), row.end(), make_pair(x, i));
        int my_idx_in_row = distance(row.begin(), it);

        int right_neighbor = (my_idx_in_row + 1 < row.size()) ? row[my_idx_in_row + 1].second : -1;
        int left_neighbor = (my_idx_in_row > 0) ? row[my_idx_in_row - 1].second : -1;

        if (obstacles[i].type == '/') {
            if(left_neighbor != -1) obstacles[i].adj.push_back(up_neighbor);
            if(up_neighbor != -1) obstacles[i].adj.push_back(left_neighbor);
            if(right_neighbor != -1) obstacles[i].adj.push_back(down_neighbor);
            if(down_neighbor != -1) obstacles[i].adj.push_back(right_neighbor);
        } else { // type == '\'
            if(left_neighbor != -1) obstacles[i].adj.push_back(down_neighbor);
            if(down_neighbor != -1) obstacles[i].adj.push_back(left_neighbor);
            if(right_neighbor != -1) obstacles[i].adj.push_back(up_neighbor);
            if(up_neighbor != -1) obstacles[i].adj.push_back(right_neighbor);
        }
         // Rút gọn lại adj, vì mỗi đỉnh chỉ có 2 cạnh ra
        sort(obstacles[i].adj.begin(), obstacles[i].adj.end());
        obstacles[i].adj.erase(remove(obstacles[i].adj.begin(), obstacles[i].adj.end(), -1), obstacles[i].adj.end());
    }
    
    // Tìm chu trình, kiểm tra và tô màu 2 phía
    bipartite_color.assign(n, -1);
    visited.assign(n, false);
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            if (!find_and_color_cycles(i, 0, obstacles)) {
                cout << -1 << endl;
                return 0;
            }
        }
    }

    // Tô 4 màu cuối cùng
    final_colors.assign(n, 0);
    vector<int> counts(2, 0);
    for (int i = 0; i < n; ++i) {
        int c = bipartite_color[i];
        final_colors[i] = (2 * c + 1) + (counts[c] % 2);
        counts[c]++;
    }

    for (int i = 0; i < n; ++i) {
        cout << final_colors[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70