Submission #1094926

#TimeUsernameProblemLanguageResultExecution timeMemory
1094926raphaelpMake them Meet (EGOI24_makethemmeet)C++14
34 / 100
5 ms864 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; } } void dfs2(int x, int p, vector<vector<int>> &AR, vector<int> &par, vector<int> &deb, vector<int> &sub, int &cur, int depth, int tree) { sub[x] = tree; par[x] = p; deb[x] = cur - depth; cur += 2; for (int i = 0; i < AR[x].size(); i++) { if (AR[x][i] == p) continue; dfs2(AR[x][i], x, AR, par, deb, sub, cur, depth + 1, tree); } } 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<int> par(N), deb(N, 1000), sub(N); 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 = 0; dfs2(AR[centre][i], centre, AR, par, deb, sub, pos, 0, i); } for (int i = 0; i < N; i++) { if (i == centre) continue; if (deb[i] == 0) { for (int j = 1; j < 400; j += 2) ans[j][i] = centre; continue; } if (sub[i] == 0) deb[i] += deb[i] / 2; if (sub[i] == 1) { deb[i] += deb[i] / 2; deb[i] += 2; } for (int j = deb[i] + 1; j < 400; j += 2) { ans[j][i] = par[i]; if (sub[i] <= 1) j += 2; } } 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; } }

Compilation message (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 'void dfs2(int, int, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&, std::vector<int>&, int&, int, int)':
Main.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     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:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:94:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             for (int k = 0; k < AR2[i].size(); k++)
      |                             ~~^~~~~~~~~~~~~~~
Main.cpp:96:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             for (int k = 0; k < AR2[j].size(); k++)
      |                             ~~^~~~~~~~~~~~~~~
Main.cpp:146:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for (int j = 0; j < AR2[leaf].size(); j++)
      |                     ~~^~~~~~~~~~~~~~~~~~
Main.cpp:148:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for (int i = 0; i < AR2[centre].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:158:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |             for (int j = 0; j < AR2[AR2[centre][i]].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:166:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |         for (int j = 0; j < AR2[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
Main.cpp:186:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     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...