#include <cstdio>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <tuple>
#include <cmath>
#include <cassert>
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;
*/
}
//for (int i = 0; i < )
//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
checker.cpp: In function 'int main()':
checker.cpp:46: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:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", temps);
~~~~~^~~~~~~~~~~~~~
checker.cpp:76: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 time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
6136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
6136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
