#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 <= 3) {
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];
}
}
void locate(vector<pair<int, int>> F, int curr, int t) {
curr --;
int N = F.size() + 1;
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);
}
if (N == 2) {
if (t == 1) return;
visit(adj[curr][0] + 1);
return;
}
if (N == 3) {
if (t == 1) return;
int mid;
for (int i=0; i<3; i++) {
if (adj[i].size() == 2) {
mid = i;
break;
}
}
if (mid == curr) {
int l = curr == 0 ? 1 : 0;
if (visit(l + 1)) return;
visit(mid + 1);
visit(3-l-mid + 1);
return;
}
else {
if (visit(mid + 1)) return;
visit(3-curr-mid + 1);
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 < 3) {
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 < 3) {
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;
}
/*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];
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 >= 3);
for (int i=0; i<3-lcnt; i++) {
color[rs[i]] = visit(rs[i] + 1);
}
for (int i=1-lcnt; i>=0; i--) {
visit(rs[i] + 1);
}
if (lcnt < 3)
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<3-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;
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<4; 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];
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;
}
}
}
}
}
/*
using namespace std;
typedef pair<int, int> edge;
constexpr int VISIT = 473895279, ANSWER = 1979520194;
#define VISITING_ALICE "Alice must not call visit"
#define TOO_MANY_VISITS "Bob called visit too often"
#define WRONG_ANSWER "Wrong answer"
#define INVALID_ALICE "Return value of alice invalid"
#define TOO_MANY_TIES "Too many ties in one room"
#define INVALID_VISIT "Invalid call to visit"
#define CORRECT(x,y) "Correct: %d extra visits, Kmax = %d", (x), (y)
#define SECURITY_VIOLATION "Security violation!"
vector<pair<int, float>> _score = {make_pair(1, 1.0f), make_pair(2, 0.4f), make_pair(1000000000, 0.3f)};
void result(double points, const char *msg, ...) {
va_list args;
va_start(args, msg);
vprintf(msg, args);
va_end(args);
printf("\n");
if (points <= 0) {
exit(0);
}
if (points < 1) {
printf("Partially correct: %.2f%%\n", points * 100);
}else {
printf("Correct\n");
}
exit(0);
}
class basic_adversary {
public:
basic_adversary(vector<edge> E, int d) :
edges(E), N(E.size() + 1), dest(d), T(N) {
for(auto [a, b] : edges)
T[a].push_back(b), T[b].push_back(a);
}
~basic_adversary() {}
vector<edge> edges_1indexed() {
vector<edge> E;
for(auto [a, b] : edges)
E.emplace_back(a + 1, b + 1);
return E;
}
pair<vector<edge>, int> for_alice() {
return {edges_1indexed(), dest};
}
tuple<vector<edge>, int, int, int> for_bob() {
return make_tuple(edges_1indexed(), curr_node + 1, ids[curr_node], dist(curr_node, dest-1));
}
void answer_alice(vector<int> v) { ids = v; }
bool answer_bob() { return dest-1 == curr_node; } // should we check whether the solution is unique?
int visit(int v) {
if(!connected(curr_node, v)) return -1;
curr_node = v;
return ids[curr_node];
}
int get_N() { return N; }
void set_curr_node(int v) { curr_node = v; }
protected:
vector<int> ids;
vector<edge> edges;
int N;
int dest;
int curr_node;
vector<vector<int>> T;
int dist(int a, int b) {
stack<int> s; s.push(a);
vector<int> dist(T.size(), -1); dist[a] = 0;
while(!s.empty()) {
int x = s.top(); s.pop();
for(int w : T[x])
if(dist[w] < 0)
dist[w] = dist[x] + 1, s.push(w);
}
return dist[b];
}
bool connected(int v, int w) {
for(int x : T[v])
if(x == w) return true;
return false;
}
};
enum { ALICE = 1337, BOB = 4242 } who;
basic_adversary *adv;
int N;
int Kmax = 0;
int S = 30, counter = 0;
float score(int k) {
for(auto [bound, s] : _score)
if(k <= bound) return s;
assert(false);
return 0.0;
}
void handle_answer_bob() {
if(adv->answer_bob()) result(score(Kmax), CORRECT(counter, Kmax));
else result(0.0, WRONG_ANSWER);
}
void handle_alice() {
who = ALICE;
// Send Alice the tree and the secret node
auto [T, dest] = adv->for_alice();
vector<int> ids = mark(T, dest);
if (ids.size() != N) result(0.0, INVALID_ALICE);
printf("mark(F, safe) returned:");
for(int x : ids) {
if(x < 0) result(0.0, INVALID_ALICE);
Kmax = max(Kmax, x);
printf(" %d", x);
}
printf("\n");
if(Kmax > _score.back().first) result(0.0, TOO_MANY_TIES);
adv->answer_alice(ids);
}
int visit(int w) {
if(who != BOB) {
result(0.0, VISITING_ALICE);
}
++counter;
if(counter > S) result(0.0, TOO_MANY_VISITS);
if(w < 1 or w > N) result(0.0, INVALID_VISIT);
--w;
int x = adv->visit(w);
if(x == -1) result(0.0, INVALID_VISIT);
return x;
}
void handle_bob() {
who = BOB;
auto [T, start, x, dist] = adv->for_bob();
counter -= dist;
locate(T, start, x);
handle_answer_bob();
}
int main() {
int safe;
assert(scanf("%d %d", &N, &safe) == 2);
vector<edge> edges;
for(int i = 1; i < N; ++i) {
int u, v; scanf("%d %d", &u, &v);
u -= 1; v -= 1;
edges.emplace_back(u, v);
}
adv = new basic_adversary(edges, safe);
handle_alice();
int curr; scanf("%d", &curr);
curr -= 1;
adv->set_curr_node(curr);
handle_bob();
return 0;
}*/
Compilation message
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:189:17: warning: unused variable 'pos' [-Wunused-variable]
189 | int pos = seq.size();
| ^~~
incursion.cpp:266:18: warning: unused variable 'flag' [-Wunused-variable]
266 | bool flag = false;
| ^~~~
incursion.cpp:274:29: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
274 | if (sz[l] < sz[r]) swap(l, r);
| ^
incursion.cpp:270:17: warning: 'prv' may be used uninitialized in this function [-Wmaybe-uninitialized]
270 | if (y == prv) continue;
| ^~
incursion.cpp:100:25: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
100 | visit(3-curr-mid + 1);
| ~~~~~~^~~~
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 |
0 ms |
768 KB |
Correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
171 ms |
12956 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
7520 KB |
Correct |
| 2 |
Correct |
65 ms |
7580 KB |
Correct |
| 3 |
Correct |
65 ms |
7520 KB |
Correct |
| 4 |
Correct |
79 ms |
10408 KB |
Correct |
| 5 |
Correct |
117 ms |
10084 KB |
Correct |
| 6 |
Correct |
125 ms |
10500 KB |
Correct |
| 7 |
Correct |
62 ms |
7324 KB |
Correct |
| 8 |
Correct |
75 ms |
7332 KB |
Correct |
| 9 |
Correct |
60 ms |
7408 KB |
Correct |
| 10 |
Incorrect |
60 ms |
7324 KB |
Not correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
768 KB |
Correct |
| 2 |
Incorrect |
171 ms |
12956 KB |
Not correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
