#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
int visit(int w);
int rep[] = {1, 1, 0, 1, 0, 0};
int rt;
void dfs(int x, int p, int pp, int dep, vector<int> &color, vector<vector<int>> &adj) {
if (x != rt) {
if (p == rt) {
color[x] = 1;
}
else {
if (adj[p].size() == 3) {
color[x] = color[pp] ^ 1;
dep = -1;
}
else {
if (dep == -1) {
for (int i=0; i<6; i++) {
if (rep[i] == color[pp] && rep[(i+1)%6] == color[p]) {
dep = (i+2) % 6;
break;
}
}
}
color[x] = rep[dep];
}
}
}
for (auto &y : adj[x]) {
if (y == p) continue;
dfs(y, x, p, dep == -1 ? -1 : (dep+1)%6, color, adj);
}
}
vector<int> mark(vector<pair<int, int>> F, int safe) {
safe --;
int N = F.size() + 1;
if (N <= 10) {
vector<int> color(N, 0);
color[safe] = 1;
return color;
}
vector<vector<int>> adj(N);
for (int i=0; i<N-1; i++) {
adj[F[i].first - 1].push_back(F[i].second - 1);
adj[F[i].second - 1].push_back(F[i].first - 1);
}
vector<int> color(N);
rt = safe;
color[safe] = 1;
dfs(safe, -1, -1, -1, color, adj);
return color;
}
void dfs2(int x, int p, vector<int> &sz, vector<vector<int>> &adj) {
sz[x] = 1;
for (auto &y : adj[x]) {
if (y == p) continue;
dfs2(y, x, sz, adj);
sz[x] += sz[y];
}
}
bool dfs3(int x, int p, vector<int> &color, vector<vector<int>> &adj) {
if (color[x] == 1) return true;
for (auto &y : adj[x]) {
if (y == p) continue;
color[y] = visit(y + 1);
bool ret = dfs3(y, x, color, adj);
if (ret) return true;
visit(x + 1);
}
return false;
}
void locate(vector<pair<int, int>> F, int curr, int t) {
curr --;
int N = F.size() + 1;
vector<vector<int>> adj(N);
assert(N <= 10000);
for (int i=0; i<N-1; i++) {
adj[F[i].first - 1].push_back(F[i].second - 1);
adj[F[i].second - 1].push_back(F[i].first - 1);
}
if (N <= 10) {
vector<int> color(N, 0);
color[curr] = t;
dfs3(curr, -1, color, adj);
return;
}
vector<int> color(N, -1);
color[curr] = t;
if (adj[curr].size() == 1) {
t = visit(adj[curr][0] + 1);
curr = adj[curr][0];
color[curr] = t;
}
vector<int> sz(N);
dfs2(curr, -1, sz, adj);
int prv;
assert(adj[curr].size() > 1);
if (adj[curr].size() == 2) {
int l = adj[curr][0], r = adj[curr][1];
if (sz[l] < sz[r]) swap(l, r);
int lcnt = 1, rcnt = 1;
int p = curr, x = l;
vector<int> ls, rs;
ls.push_back(l);
while (lcnt < 4) {
if (adj[x].size() == 2) {
lcnt ++;
int temp = p;
p = x;
x = adj[x][0] + adj[x][1] - temp;
ls.push_back(x);
}
else break;
}
p = curr; x = r;
rs.push_back(x);
while (rcnt < 4) {
if (adj[x].size() == 2) {
rcnt ++;
int temp = p;
p = x;
x = adj[x][0] + adj[x][1] - temp;
rs.push_back(x);
}
else break;
}
assert(ls.size() == lcnt && rs.size() == rcnt);
/*for (auto &p : ls) {
printf("%d ", p);
}
printf("\n");
for (auto &p : rs) {
printf("%d ", p);
}
printf("\n");*/
if (lcnt == 1) {
color[l] = visit(l + 1);
assert(adj[l].size() == 3);
curr = l;
vector<int> col(3);
for (int i=0; i<3; i++) {
int y = adj[curr][i];
if (color[y] != -1) {
col[i] = color[y];
continue;
}
color[y] = col[i] = visit(y + 1);
visit(curr + 1);
}
int nxt;
if (col[0] == col[1] && col[1] == col[2]) return;
if (col[0] != col[1] && col[0] != col[2]) nxt = adj[curr][0];
else if (col[1] != col[0] && col[1] != col[2]) nxt = adj[curr][1];
else nxt = adj[curr][2];
visit(nxt + 1);
prv = curr;
curr = nxt;
}
else if (rcnt == 1) {
color[r] = visit(r + 1);
assert(adj[r].size() == 3);
curr = r;
vector<int> col(3);
for (int i=0; i<3; i++) {
int y = adj[curr][i];
if (color[y] != -1) {
col[i] = color[y];
continue;
}
color[y] = col[i] = visit(y + 1);
visit(curr + 1);
}
int nxt;
if (col[0] == col[1] && col[1] == col[2]) return;
if (col[0] != col[1] && col[0] != col[2]) nxt = adj[curr][0];
else if (col[1] != col[0] && col[1] != col[2]) nxt = adj[curr][1];
else nxt = adj[curr][2];
visit(nxt + 1);
prv = curr;
curr = nxt;
}
else {
assert(lcnt + rcnt >= 4);
for (int i=0; i<4-lcnt; i++) {
color[rs[i]] = visit(rs[i] + 1);
}
for (int i=2-lcnt; i>=0; i--) {
visit(rs[i] + 1);
}
if (lcnt < 4)
visit(curr + 1);
for (int i=0; i<lcnt; i++) {
color[ls[i]] = visit(ls[i] + 1);
}
vector<int> seq, vtx;
for (int i=lcnt-1; i>=0; i--) {
seq.push_back(color[ls[i]]);
vtx.push_back(ls[i]);
}
int pos = seq.size();
seq.push_back(color[curr]);
vtx.push_back(curr);
for (int i=0; i<4-lcnt; i++) {
seq.push_back(color[rs[i]]);
vtx.push_back(rs[i]);
}
/*for (auto &p : seq) {
printf("%d ", p);
}
printf("\n");
for (auto &p : vtx) {
printf("%d ", p);
}
printf("\n");*/
int safe = -1;
if (seq[0] == seq[1] && seq[1] == seq[2]) safe = 1;
else if (seq[3] == seq[1] && seq[1] == seq[2]) safe = 2;
else if (seq[2] == seq[3] && seq[3] == seq[4]) safe = 3;
if (safe != -1) {
for (int i=1; i<=safe; i++) visit(vtx[i] + 1);
return;
}
bool f1 = false;
for (int i=0; i<6; i++) {
bool f2 = true;
for (int j=0; j<5; j++) {
if (seq[j] != rep[(i+j)%6]) {
f2 = false;
break;
}
}
if (f2) {
f1 = true;
break;
}
}
if (!f1) {
visit(vtx[1] + 1);
prv = vtx[0];
curr = vtx[1];
}
else {
prv = vtx[1];
curr = vtx[0];
}
}
}
else if (adj[curr].size() == 3) {
vector<int> col(3);
for (int i=0; i<3; i++) {
int y = adj[curr][i];
if (color[y] != -1) {
col[i] = color[y];
continue;
}
color[y] = col[i] = visit(y + 1);
visit(curr + 1);
}
if (col[0] == col[1] && col[1] == col[2]) return;
int nxt;
if (col[0] != col[1] && col[0] != col[2]) nxt = adj[curr][0];
else if (col[1] != col[0] && col[1] != col[2]) nxt = adj[curr][1];
else nxt = adj[curr][2];
visit(nxt + 1);
prv = curr;
curr = nxt;
}
while (true) {
if (adj[curr].size() == 1) return;
int zero = color[prv] == 0 || color[curr] == 0;
if (adj[curr].size() == 2) {
int nxt = adj[curr][0] + adj[curr][1] - prv;
color[nxt] = visit(nxt + 1);
if (!zero && color[nxt]) {
visit(curr + 1);
return;
}
prv = curr;
curr = nxt;
}
else {
bool flag = false;
int l = -1, r;
for (int i=0; i<3; i++) {
int y = adj[curr][i];
if (y == prv) continue;
if (l == -1) l = y;
else r = y;
}
if (sz[l] < sz[r]) swap(l, r);
color[l] = visit(l + 1);
if (color[l] != color[prv]) {
prv = curr;
curr = l;
}
else {
visit(curr + 1);
color[r] = visit(r + 1);
if (color[r] != color[prv]) {
prv = curr;
curr = r;
}
else {
visit(curr + 1);
return;
}
}
}
}
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from incursion.cpp:2:
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:136:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
136 | assert(ls.size() == lcnt && rs.size() == rcnt);
| ~~~~~~~~~~^~~~~~~
incursion.cpp:136:47: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
136 | assert(ls.size() == lcnt && rs.size() == rcnt);
| ~~~~~~~~~~^~~~~~~
incursion.cpp:209:17: warning: unused variable 'pos' [-Wunused-variable]
209 | int pos = seq.size();
| ^~~
incursion.cpp:291:18: warning: unused variable 'flag' [-Wunused-variable]
291 | bool flag = false;
| ^~~~
incursion.cpp:299:29: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
299 | if (sz[l] < sz[r]) swap(l, r);
| ^
incursion.cpp:295:17: warning: 'prv' may be used uninitialized in this function [-Wmaybe-uninitialized]
295 | if (y == prv) continue;
| ^~
interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
44 | if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
50 | int l = (numbers.size() == N ? N : 0);
| ~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
764 KB |
Correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
11176 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
7524 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
764 KB |
Correct |
| 2 |
Runtime error |
62 ms |
11176 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
