제출 #940737

#제출 시각아이디문제언어결과실행 시간메모리
940737evenvalue게임 (IOI14_game)C++17
42 / 100
1022 ms72380 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>; template<typename T> using max_heap = priority_queue<T, vector<T>, less<T>>; using int64 = long long; using ld = long double; constexpr int kInf = 1e9 + 10; constexpr int64 kInf64 = 1e15 + 10; constexpr int kMod = 1e9 + 7; class dsu { int n; std::vector<int> e; int pfind(const int x) { return (e[x] < 0 ? x : e[x] = pfind(e[x])); } public: dsu() : n(0), comp(0) {} explicit dsu(const int n) : n(n), comp(n), e(n, -1) {} int comp; int find(const int x) { assert(0 <= x and x < n); return pfind(x); } bool unite(int x, int y) { x = find(x), y = find(y); if (x == y) return false; if (e[x] > e[y]) swap(x, y); e[x] += e[y]; e[y] = x; comp--; return true; } bool same(const int x, const int y) { return (find(x) == find(y)); } int size(const int x) { return -e[find(x)]; } std::vector<std::vector<int>> components() { std::vector<std::vector<int>> res(n); for (int x = 0; x < n; x++) { res[pfind(x)].push_back(x); } res.erase( std::remove_if(res.begin(), res.end(), [&](const std::vector<int> &v) { return v.empty(); }), res.end()); return res; } }; int n; dsu d; set<int> leaders; vector<map<int, int>> edges; void initialize(const int N) { n = N; d = dsu(n); for (int x = 0; x < n; x++) { leaders.insert(x); } edges = vector<map<int, int>>(n); } int hasEdge(int x, int y) { x = d.find(x); y = d.find(y); edges[x][y]++, edges[y][x]++; const int cur = edges[x][y]; const int req = d.size(x) * d.size(y); if (cur == req) { d.unite(x, y); if (x != d.find(x)) swap(x, y); leaders.erase(y); for (const int z : leaders) { edges[x][z] += edges[y][z]; edges[z][x] += edges[z][y]; edges[z].erase(y); } } return (cur == req); }

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

game.cpp: In constructor 'dsu::dsu(int)':
game.cpp:29:7: warning: 'dsu::comp' will be initialized after [-Wreorder]
   29 |   int comp;
      |       ^~~~
game.cpp:19:20: warning:   'std::vector<int> dsu::e' [-Wreorder]
   19 |   std::vector<int> e;
      |                    ^
game.cpp:27:12: warning:   when initialized here [-Wreorder]
   27 |   explicit dsu(const int n) : n(n), comp(n), e(n, -1) {}
      |            ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...