Submission #1246767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246767		vht2025	Fliper (COCI22_fliper)	C++20	0 / 110	654 ms	50176 KiB

Main

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

using namespace std;

struct Obstacle {
    int id;
    int u_coord_id, v_coord_id;
};

vector<int> adj[1000005];
vector<int> bipartite_color;
vector<bool> visited;

// DFS để tìm thành phần liên thông và tô màu 2 phía
void color_component(int start_node, int color, int& node_count, int& edge_count, vector<bool>& component_visited) {
    bipartite_color[start_node] = color;
    component_visited[start_node] = true;
    node_count++;
    edge_count += adj[start_node].size();

    for (int neighbor : adj[start_node]) {
        if (!component_visited[neighbor]) {
            color_component(neighbor, 1 - color, node_count, edge_count, component_visited);
        }
    }
}

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

    int n;
    cin >> n;

    vector<Obstacle> obstacles(n);
    map<int, int> u_map, v_map;
    vector<pair<int, int>> edges;

    // Rời rạc hóa tọa độ u, v
    for (int i = 0; i < n; ++i) {
        int x, y;
        char type;
        cin >> x >> y >> type;
        u_map[x + y] = 0;
        v_map[x - y] = 0;
        edges.push_back({x + y, x - y});
    }

    int u_nodes = 0;
    for (auto& pair : u_map) {
        pair.second = u_nodes++;
    }
    int v_nodes = 0;
    for (auto& pair : v_map) {
        pair.second = u_nodes + v_nodes++;
    }

    int total_nodes = u_nodes + v_nodes;

    // Xây dựng đồ thị hai phía
    for (int i = 0; i < n; ++i) {
        obstacles[i].id = i;
        obstacles[i].u_coord_id = u_map[edges[i].first];
        obstacles[i].v_coord_id = u_map.size() + v_map[edges[i].second];
        int u_node = u_map[edges[i].first];
        int v_node = v_map[edges[i].second] + u_nodes;
        adj[u_node].push_back(v_node);
        adj[v_node].push_back(u_node);
    }
    
    // Tìm chu trình, kiểm tra và tô màu
    visited.assign(total_nodes, false);
    for (int i = 0; i < total_nodes; ++i) {
        if (!visited[i] && !adj[i].empty()) {
            int node_count = 0;
            long long edge_sum_degree = 0;
            vector<int> component_nodes;
            
            vector<int> q;
            q.push_back(i);
            visited[i] = true;
            int head = 0;
            while(head < q.size()){
                int u = q[head++];
                component_nodes.push_back(u);
                edge_sum_degree += adj[u].size();
                for(int v : adj[u]){
                    if(!visited[v]){
                        visited[v] = true;
                        q.push_back(v);
                    }
                }
            }
            node_count = component_nodes.size();

            // Một thành phần liên thông là một chu trình (hoặc tập các chu trình)
            // nếu bậc của mọi đỉnh là 2. Tương đương tổng bậc = 2 * số đỉnh.
            if (edge_sum_degree != (long long)node_count * 2) {
                continue; // Là một đường đi, không phải chu trình
            }

            int cycle_len = node_count; // Trong đồ thị hai phía, số cạnh bằng số đỉnh trong một chu trình đơn
            if (cycle_len % 4 != 0) { // L_bipartite = L_pinball / 2
                cout << -1 << endl;
                return 0;
            }
        }
    }
    
    // Tô màu 2 phía
    bipartite_color.assign(total_nodes, -1);
    for (int i = 0; i < total_nodes; ++i) {
        if (bipartite_color[i] == -1 && !adj[i].empty()) {
            vector<bool> component_visited(total_nodes, false);
            int node_count = 0, edge_count = 0;
            color_component(i, 0, node_count, edge_count, component_visited);
        }
    }

    // Tô 4 màu cuối cùng
    vector<int> final_colors(n);
    vector<int> counts(2, 0); // Đếm cho mỗi phía của đồ thị 2 màu
    for (int i = 0; i < n; ++i) {
        int u_node = obstacles[i].u_coord_id;
        int c = bipartite_color[u_node];
        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