Submission #1253358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253358		vuviet	World Map (IOI25_worldmap)	C++20	Compilation error	0 ms	0 KiB

worldmap

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

typedef vector<int> vi;

vector<vi> create_map(int n, int m, vi a, vi b) {
    vector<vi> adj(n + 1);
    for (int i = 0; i < m; i++) {
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }

    // Step 1: Build DFS tree
    vi parent(n + 1, 0), depth(n + 1, 0);
    vector<vi> child(n + 1);
    function<void(int)> dfs = [&](int u) {
        for (int v : adj[u]) {
            if (v == parent[u]) continue;
            if (parent[v]) continue;
            parent[v] = u;
            depth[v] = depth[u] + 1;
            child[u].push_back(v);
            dfs(v);
        }
    };
    parent[1] = -1;
    dfs(1);

    // Step 2: Euler tour
    vi dfs_ord;
    function<void(int)> dfs_euler = [&](int u) {
        dfs_ord.push_back(u);
        for (int v : child[u]) {
            dfs_euler(v);
            dfs_ord.push_back(u);
        }
    };
    dfs_euler(1); // size = 2n - 1

    // Step 3: Tin/tout for ancestor check
    int timer = 0;
    vi tin(n + 1), tout(n + 1);
    function<void(int)> dfs_time = [&](int u) {
        tin[u] = ++timer;
        for (int v : child[u]) dfs_time(v);
        tout[u] = timer;
    };
    dfs_time(1);

    // Step 4: Build "need" array for back edges
    vector<vi> need(n + 1);
    for (int i = 0; i < m; i++) {
        int u = a[i], v = b[i];
        if (parent[v] == u || parent[u] == v) continue;
        if (tin[v] < tin[u] && tout[v] > tout[u]) swap(u, v);
        need[v].push_back(u);
    }

    // Step 5: Build rows for diagonals
    vector<vi> rows;
    vector<bool> seen(n + 1);
    for (int u : dfs_ord) {
        rows.push_back({u});
        if (!seen[u] && !need[u].empty()) {
            rows.push_back(need[u]);
            rows.push_back({u});
            seen[u] = true;
        }
    }

    while ((int)rows.size() < 4 * n - 1)
        rows.push_back(rows.back());

    // Step 6: Fill grid along diagonals x + y = i
    int K = 4 * n;
    vector<vi> grid(K, vi(K, 0));
    for (int i = 0; i < 4 * n - 1; i++) {
        int len = min(i + 1, 4 * n - 1 - i);
        while ((int)rows[i].size() < len)
            rows[i].push_back(rows[i].back());
        int p = 0;
        for (int x = 0; x < K; x++) {
            int y = i - x;
            if (0 <= y && y < K && p < len)
                grid[x][y] = rows[i][p++];
        }
    }

    // Step 7: Fill any remaining 0s with color 1 (safe)
    for (int i = 0; i < K; i++)
        for (int j = 0; j < K; j++)
            if (grid[i][j] == 0) grid[i][j] = 1;

    // Optional: validate (assert all 3 conditions)
    set<pair<int,int>> allowed;
    for (int i = 0; i < m; i++) {
        allowed.insert({a[i], b[i]});
        allowed.insert({b[i], a[i]});
    }
    for (int i = 1; i <= n; i++) allowed.insert({i, i});

    // 1. Every country must appear
    vector<bool> appears(n + 1, false);
    for (int r = 0; r < K; r++)
        for (int c = 0; c < K; c++)
            appears[grid[r][c]] = true;
    for (int i = 1; i <= n; i++)
        assert(appears[i]);

    // 2. Every (a[i], b[i]) must appear as neighbors
    set<pair<int,int>> seen;
    int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
    for (int r = 0; r < K; r++) {
        for (int c = 0; c < K; c++) {
            int u = grid[r][c];
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr < 0 || nr >= K || nc < 0 || nc >= K) continue;
                int v = grid[nr][nc];
                if (u != v) seen.insert({u, v});
            }
        }
    }
    for (int i = 0; i < m; i++) {
        assert(seen.count({a[i], b[i]}) || seen.count({b[i], a[i]}));
    }

    // 3. No invalid neighbor pairs
    for (int r = 0; r < K; r++) {
        for (int c = 0; c < K; c++) {
            int u = grid[r][c];
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr < 0 || nr >= K || nc < 0 || nc >= K) continue;
                int v = grid[nr][nc];
                if (u != v) {
                    assert(allowed.count({u, v}));
                }
            }
        }
    }

    return grid;
}

Compilation message (stderr)

worldmap.cpp: In function 'std::vector<std::vector<int> > create_map(int, int, vi, vi)':
worldmap.cpp:111:24: error: conflicting declaration 'std::set<std::pair<int, int> > seen'
  111 |     set<pair<int,int>> seen;
      |                        ^~~~
worldmap.cpp:61:18: note: previous declaration as 'std::vector<bool> seen'
   61 |     vector<bool> seen(n + 1);
      |                  ^~~~
worldmap.cpp:120:40: error: no matching function for call to 'std::vector<bool>::insert(<brace-enclosed initializer list>)'
  120 |                 if (u != v) seen.insert({u, v});
      |                             ~~~~~~~~~~~^~~~~~~~
In file included from /usr/include/c++/11/vector:68,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from worldmap.cpp:1:
/usr/include/c++/11/bits/stl_bvector.h:1016:9: note: candidate: 'template<class _InputIterator, class> std::vector<bool, _Alloc>::iterator std::vector<bool, _Alloc>::insert(std::vector<bool, _Alloc>::const_iterator, _InputIterator, _InputIterator) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Alloc = std::allocator<bool>]'
 1016 |         insert(const_iterator __position,
      |         ^~~~~~
/usr/include/c++/11/bits/stl_bvector.h:1016:9: note:   template argument deduction/substitution failed:
worldmap.cpp:120:40: note:   candidate expects 3 arguments, 1 provided
  120 |                 if (u != v) seen.insert({u, v});
      |                             ~~~~~~~~~~~^~~~~~~~
In file included from /usr/include/c++/11/vector:68,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from worldmap.cpp:1:
/usr/include/c++/11/bits/stl_bvector.h:998:7: note: candidate: 'std::vector<bool, _Alloc>::iterator std::vector<bool, _Alloc>::insert(std::vector<bool, _Alloc>::const_iterator, const bool&) [with _Alloc = std::allocator<bool>; std::vector<bool, _Alloc>::iterator = std::vector<bool>::iterator; std::vector<bool, _Alloc>::const_iterator = std::vector<bool>::const_iterator]' (near match)
  998 |       insert(const_iterator __position, const bool& __x = bool())
      |       ^~~~~~
/usr/include/c++/11/bits/stl_bvector.h:998:7: note:   conversion of argument 1 would be ill-formed:
worldmap.cpp:120:42: error: invalid conversion from 'int' to 'std::_Bit_type*' {aka 'long unsigned int*'} [-fpermissive]
  120 |                 if (u != v) seen.insert({u, v});
      |                                          ^
      |                                          |
      |                                          int
In file included from /usr/include/c++/11/vector:68,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from worldmap.cpp:1:
/usr/include/c++/11/bits/stl_bvector.h:336:37: note:   initializing argument 1 of 'std::_Bit_const_iterator::_Bit_const_iterator(std::_Bit_type*, unsigned int)'
  336 |     _Bit_const_iterator(_Bit_type * __x, unsigned int __y)
      |                         ~~~~~~~~~~~~^~~
worldmap.cpp:120:45: warning: narrowing conversion of 'v' from 'int' to 'unsigned int' [-Wnarrowing]
  120 |                 if (u != v) seen.insert({u, v});
      |                                             ^
In file included from /usr/include/c++/11/vector:68,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from worldmap.cpp:1:
/usr/include/c++/11/bits/stl_bvector.h:1039:7: note: candidate: 'std::vector<bool, _Alloc>::iterator std::vector<bool, _Alloc>::insert(std::vector<bool, _Alloc>::const_iterator, std::vector<bool, _Alloc>::size_type, const bool&) [with _Alloc = std::allocator<bool>; std::vector<bool, _Alloc>::iterator = std::vector<bool>::iterator; std::vector<bool, _Alloc>::const_iterator = std::vector<bool>::const_iterator; std::vector<bool, _Alloc>::size_type = long unsigned int]'
 1039 |       insert(const_iterator __position, size_type __n, const bool& __x)
      |       ^~~~~~
/usr/include/c++/11/bits/stl_bvector.h:1039:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/11/bits/stl_bvector.h:1053:7: note: candidate: 'std::vector<bool, _Alloc>::iterator std::vector<bool, _Alloc>::insert(std::vector<bool, _Alloc>::const_iterator, std::initializer_list<bool>) [with _Alloc = std::allocator<bool>; std::vector<bool, _Alloc>::iterator = std::vector<bool>::iterator; std::vector<bool, _Alloc>::const_iterator = std::vector<bool>::const_iterator]'
 1053 |       insert(const_iterator __p, initializer_list<bool> __l)
      |       ^~~~~~
/usr/include/c++/11/bits/stl_bvector.h:1053:7: note:   candidate expects 2 arguments, 1 provided
In file included from /usr/include/c++/11/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from worldmap.cpp:1:
worldmap.cpp:125:21: error: 'class std::vector<bool>' has no member named 'count'
  125 |         assert(seen.count({a[i], b[i]}) || seen.count({b[i], a[i]}));
      |                     ^~~~~
worldmap.cpp:125:49: error: 'class std::vector<bool>' has no member named 'count'
  125 |         assert(seen.count({a[i], b[i]}) || seen.count({b[i], a[i]}));
      |                                                 ^~~~~