제출 #1094935

#제출 시각아이디문제언어결과실행 시간메모리
1094935raphaelpMake them Meet (EGOI24_makethemmeet)C++14
100 / 100
8 ms1112 KiB
#include <bits/stdc++.h> using namespace std; class UnionFind { private: vector<int> p; public: UnionFind(int x) { p.assign(x, 0); for (int i = 0; i < x; i++) p[i] = i; } int find(int x) { return (x == p[x]) ? x : p[x] = find(p[x]); } bool merge(int a, int b) { int x = find(a), y = find(b); if (x == y) return 0; p[x] = y; return 1; } }; void dfs(int x, int p, vector<vector<int>> &AR, vector<vector<int>> &ans, int &cur, int &last) { if (x != last) { ans[cur][x] = last; cur++; last = x; } for (int i = 0; i < AR[x].size(); i++) { if (AR[x][i] == p) continue; dfs(AR[x][i], x, AR, ans, cur, last); ans[cur][x] = last; cur++; last = x; } } int dfs2(int x, int p, vector<vector<int>> &AR, vector<vector<int>> &ans, int &cur, int depth, int add) { int sub = 1, pos = cur - depth; cur += add; for (int i = 0; i < AR[x].size(); i++) { if (AR[x][i] == p) continue; sub += dfs2(AR[x][i], x, AR, ans, cur, depth + 1, add); } for (int i = 0; i < sub; i++) { ans[pos][x] = p; pos += add; } return sub; } void dfs3(int x, vector<int> &occ, vector<vector<int>> &AR, int &num, int nono) { num++; occ[x] = 1; for (int i = 0; i < AR[x].size(); i++) { if (occ[AR[x][i]]) continue; if (AR[x][i] == nono) continue; dfs3(AR[x][i], occ, AR, num, nono); } } int main() { int N, M; cin >> N >> M; vector<vector<int>> AR(N), AR2(N); UnionFind UF(N); for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; AR2[a].push_back(b); AR2[b].push_back(a); } int centre = -1, leaf = -1; vector<int> banned(N); for (int i = 0; i < N; i++) { if (centre != -1) break; for (int j = 0; j < N; j++) { if (centre != -1) break; vector<int> temp(N); for (int k = 0; k < AR2[i].size(); k++) temp[AR2[i][k]] = 1; for (int k = 0; k < AR2[j].size(); k++) temp[AR2[j][k]] = 0; if (temp[j] == 0) continue; for (int k = 0; k < N; k++) { if (temp[k] && k != j && k != i) { centre = i; leaf = j; } } } } if (centre == -1) { int N2 = N; if (N % 2 == 0) N2++; vector<int> perm(N2), C(N2); for (int i = 0; i < N2; i++) { perm[i] = i; if (i <= N2 / 2) { C[i] = i; C[N2 - i - 1] = i; } } cout << 2 * N2 << endl; for (int i = 0; i < N2; i++) { for (int k = 0; k < 2; k++) { for (int j = 0; j < N; j++) { cout << C[perm[j]] << ' '; } cout << '\n'; } swap(perm[0], perm[N2 - 1]); for (int j = 1; j < N2 - 1; j++) swap(perm[j], perm[j - 1]); } return 0; } UF.merge(centre, leaf); AR[centre].push_back(leaf); AR[leaf].push_back(centre); for (int j = 0; j < AR2[leaf].size(); j++) banned[AR2[leaf][j]] = 1; for (int i = 0; i < AR2[centre].size(); i++) { if (AR2[centre][i] == leaf) continue; if (banned[AR2[centre][i]]) continue; if (UF.merge(centre, AR2[centre][i])) { AR[centre].push_back(AR2[centre][i]); AR[AR2[centre][i]].push_back(centre); for (int j = 0; j < AR2[AR2[centre][i]].size(); j++) banned[AR2[AR2[centre][i]][j]] = 1; } } for (int i = 0; i < N; i++) { if (i == centre) continue; for (int j = 0; j < AR2[i].size(); j++) { if (AR2[i][j] == centre) continue; if (UF.merge(i, AR2[i][j])) { AR[i].push_back(AR2[i][j]); AR[AR2[i][j]].push_back(i); } } } vector<vector<int>> ans(600, vector<int>(N)); for (int i = 0; i < 600; i++) for (int j = 0; j < N; j++) ans[i][j] = j; for (int i = 0; i < 200; i++) { ans[i * 2][AR[centre][i % 2]] = centre; } for (int i = 0; i < AR[centre].size(); i++) { int pos = 1; if (i == 0) pos += 2; int temp = dfs2(AR[centre][i], centre, AR, ans, pos, 0, (i <= 1) ? 4 : 2); } for (int i = 0; i < AR[centre].size(); i++) { for (int j = 1; j < 400; j += 2) ans[j][AR[centre][i]] = centre; } int cur = 400, last = centre; dfs(centre, centre, AR, ans, cur, last); cout << 600 << endl; for (int i = 0; i < 600; i++) { for (int j = 0; j < N; j++) { cout << ans[i][j] << ' '; } cout << endl; } }

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

Main.cpp: In function 'void dfs(int, int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, int&, int&)':
Main.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
Main.cpp: In function 'int dfs2(int, int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, int&, int, int)':
Main.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
Main.cpp: In function 'void dfs3(int, std::vector<int>&, std::vector<std::vector<int> >&, int&, int)':
Main.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:98:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             for (int k = 0; k < AR2[i].size(); k++)
      |                             ~~^~~~~~~~~~~~~~~
Main.cpp:100:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for (int k = 0; k < AR2[j].size(); k++)
      |                             ~~^~~~~~~~~~~~~~~
Main.cpp:150:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |     for (int j = 0; j < AR2[leaf].size(); j++)
      |                     ~~^~~~~~~~~~~~~~~~~~
Main.cpp:152:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     for (int i = 0; i < AR2[centre].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:162:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |             for (int j = 0; j < AR2[AR2[centre][i]].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:170:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |         for (int j = 0; j < AR2[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
Main.cpp:189:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |     for (int i = 0; i < AR[centre].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:194:13: warning: unused variable 'temp' [-Wunused-variable]
  194 |         int temp = dfs2(AR[centre][i], centre, AR, ans, pos, 0, (i <= 1) ? 4 : 2);
      |             ^~~~
Main.cpp:196:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |     for (int i = 0; i < AR[centre].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...