Submission #223543

#TimeUsernameProblemLanguageResultExecution timeMemory
223543maomao90Checker (COCI19_checker)C++14
110 / 110
124 ms19696 KiB
#include <cstdio> #include <algorithm> #include <utility> #include <unordered_map> #include <tuple> #include <cmath> #include <cassert> #include <vector> using namespace std; typedef pair <int, int> ii; typedef pair <ii, int> iii; struct pair_hash { template <class T1, class T2> std::size_t operator() (const std::pair<T1, T2> &pair) const { return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second); } }; int tc; int N; char temps[200005]; iii diagonals[200005]; vector <iii> countSort[200005]; //unordered_map <ii, int, pair_hash> colours; bool isInvalid[200005]; ii impt1[200005], impt2[200005]; bool comp(iii right, iii left) { int rx, ry, lx, ly; tie(rx, ry) = right.first; tie(lx, ly) = left.first; if (abs(rx - ry) < abs(lx - ly)) return true; else if (abs(rx - ry) == abs(lx - ly)) { if (rx < ry) return true; } return false; } int main() { scanf("%d%d", &tc, &N); scanf(" %s", temps); for (int i = 1; i <= N; i++) { char temp = temps[i - 1]; /* if (i == N) { colours[ii(i, 1)] = (int) temp - '0'; colours[ii(1, i)] = (int) temp - '0'; } else { colours[ii(i, i + 1)] = (int) temp - '0'; colours[ii(i + 1, i)] = (int) temp - '0'; } */ if (i == N) { impt1[i] = ii(1, temp - '0'); impt2[1] = ii(i, temp - '0'); } else { impt1[i] = ii(i + 1, temp - '0'); impt2[i + 1] = ii(i, temp - '0'); } } for (int i = 0; i < N - 3; i++) { int X, Y, C; scanf("%d%d%d", &X, &Y, &C); if (X > Y) swap(X, Y); diagonals[i] = iii(ii(X, Y), C); countSort[abs(X - Y)].push_back(iii(ii(X, Y), C)); /* colours[ii(X, Y)] = C; colours[ii(Y, X)] = C; */ } int pointer = 0; for (int i = 0; i < N + 5; i++) { for (iii xyc : countSort[i]) diagonals[pointer++] = xyc; } //sort(diagonals, diagonals + N - 3, comp); for (int i = 0; i < N - 3; i++) { int x, y, c; tie(x, y) = diagonals[i].first; c = diagonals[i].second; if (isInvalid[x] || isInvalid[y]) { printf("neispravna triangulacija\n"); return 0; } int impt; if (impt1[x].first == impt1[y].first || impt1[x].first == impt2[y].first) impt = impt1[x].first; else impt = impt2[x].first; isInvalid[impt] = true; if (impt1[x].first == impt) impt1[x] = ii(y, c); else impt2[x] = ii(y, c); if (impt1[y].first == impt) impt1[y] = ii(x, c); else impt2[y] = ii(x, c); } for (int i = 1; i <= N; i++) { char temp = temps[i - 1]; /* if (i == N) { colours[ii(i, 1)] = (int) temp - '0'; colours[ii(1, i)] = (int) temp - '0'; } else { colours[ii(i, i + 1)] = (int) temp - '0'; colours[ii(i + 1, i)] = (int) temp - '0'; } */ if (i == N) { impt1[i] = ii(1, temp - '0'); impt2[1] = ii(i, temp - '0'); } else { impt1[i] = ii(i + 1, temp - '0'); impt2[i + 1] = ii(i, temp - '0'); } } for (int i = 0; i < N - 3; i++) { int x, y, c; tie(x, y) = diagonals[i].first; c = diagonals[i].second; int impt, c1, c2; if (impt1[x].first == impt1[y].first || impt1[x].first == impt2[y].first) { impt = impt1[x].first; c1 = impt1[x].second; c2 = impt1[y].first == impt ? impt1[y].second : impt2[y].second; } else { impt = impt2[x].first; c1 = impt2[x].second; c2 = impt1[y].first == impt ? impt1[y].second : impt2[y].second; } if (c == c1 || c == c2 || c1 == c2) { printf("neispravno bojenje\n"); return 0; } if (impt1[x].first == impt) impt1[x] = ii(y, c); else impt2[x] = ii(y, c); if (impt1[y].first == impt) impt1[y] = ii(x, c); else impt2[y] = ii(x, c); } printf("tocno\n"); return 0; }

Compilation message (stderr)

checker.cpp: In function 'int main()':
checker.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &tc, &N);
     ~~~~~^~~~~~~~~~~~~~~~~
checker.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", temps);
     ~~~~~^~~~~~~~~~~~~~
checker.cpp:77:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int X, Y, C; scanf("%d%d%d", &X, &Y, &C);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...