제출 #558138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558138		Olympia	게임 (IOI14_game)	C++17	컴파일 에러	0 ms	0 KiB

game

#include <bits/stdc++.h>
//#include <game.h>
using namespace std;
struct dsu {
    vector<int> parent;
    vector<int> compSize;
    int n;
    int cc;
    void fill(){
        cc = n;
        parent.resize(n), compSize.resize(n);
        for(int i = 0; i < n; i++){
            parent[i] = i, compSize[i] = 1;
        }
    }
    int find_head(int x){
        if(x == parent[x]){
            return x;
        }
        return find_head(parent[x]);
    }
    void join(int x, int y){
        x = find_head(x);
        y = find_head(y);
        if(x == y){
            return;
        }
        cc--;
        if(compSize[x] > compSize[y]){
            swap(x,y);
        }
        parent[x] = y;
        compSize[y] += compSize[x]; 
    }
    bool comp(int x, int y){
        return (find_head(x) == find_head(y));
    }
};
set<pair<int,int> > edges;
set<pair<int,int> > e;
dsu d;
void initialize (int n)  {
    d.n = n;
    d.fill();
    vector<int> vec;
    for (int i = 0; i < n; i++) {
        vec.push_back(i);
    }
    shuffle(vec.begin(), vec.end());
    for (int i: vec) {
        for (int j: vec) {
            if (!d.comp(i, j)) {
                d.join(i, j);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                e.insert(make_pair(min(i, j), max(i, j)));
            }
        }
    }
}
int hasEdge (int u, int v) {
    assert(edges.size() == d.n - 1);
    if (!edges.count(make_pair(u, v)) && !edges.count(make_pair(v, u))) {
        e.erase(make_pair(min(u, v), max(u, v)));
        return false;
    }
    d.fill();
    for (auto& p: edges) {
        if (p != make_pair(u, v) && p != make_pair(v, u)) {
            d.join(p.first, p.second);
        }
    }
    assert(d.cc == 2);
    for (auto& p: e) {
        if (p == make_pair(u, v) || p == make_pair(v, u)) continue;
        if (!d.comp(p.first, p.second)) {
            edges.erase(make_pair(min(u, v), max(u, v)));
            e.erase(make_pair(min(u, v), max(u, v)));
            edges.insert(p);
            return false;
        }
    }
    return true;
}
int main() {
    initialize(4);
    cout << hasEdge(0, 1) << '\n';
    cout << hasEdge(0, 3) << '\n';
    cout << hasEdge(1, 3) << '\n';
    cout << hasEdge(1, 2) << '\n';
    cout << hasEdge(2, 0) << '\n';
    cout << hasEdge(2, 3) << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In function 'void initialize(int)':
game.cpp:49:35: error: no matching function for call to 'shuffle(std::vector<int>::iterator, std::vector<int>::iterator)'
   49 |     shuffle(vec.begin(), vec.end());
      |                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from game.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3748:5: note: candidate: 'template<class _RAIter, class _UGenerator> void std::shuffle(_RAIter, _RAIter, _UGenerator&&)'
 3748 |     shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
      |     ^~~~~~~
/usr/include/c++/10/bits/stl_algo.h:3748:5: note:   template argument deduction/substitution failed:
game.cpp:49:35: note:   candidate expects 3 arguments, 2 provided
   49 |     shuffle(vec.begin(), vec.end());
      |                                   ^
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from game.cpp:1:
game.cpp: In function 'int hasEdge(int, int)':
game.cpp:66:25: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |     assert(edges.size() == d.n - 1);
      |            ~~~~~~~~~~~~~^~~~~~~~~~