#include <bits/stdc++.h>
#include "Joi.h"
using namespace std;
// #define LOCAL
#define maxn 10010
#define adj SPENCER_COMPTON
#define n spence
#define m king_of_hottub
#define par king_of_sice
#define label king_of_ditch
#define seen double_desk
#define desired guuuuu
#define dep blahblahblahblah
#define maxd guuuuuuuuuuuu
#define dfs guuu
#define findset gkadsflk
#define unionset dsflkasdh
#define gobig king_of_tinder
#define preorder ihatethis
#define postorder nocompile
#define dfs2 adsklf
#define gosmall PATEL
vector<vector<int>> adj(maxn);
int n;
int m;
int par[maxn];
int dep[maxn];
int label[maxn]; //which bit i correspond to
int seen = 0; //we can just use seen for making desired and labeling it
bool desired[maxn];
long long x2;
int maxd = 0;
void dfs(int u, int p) {
dep[u] = p == - 1 ? 1 : dep[p]+1;
maxd = max(maxd, dep[u]);
for (int v : adj[u]) {
if (v == p) continue;
dfs(v, u);
}
}
int findset(int u) {
if (par[u] == u) return u;
return par[u] = findset(par[u]);
}
void unionset(int a, int b) {
a = findset(a);
b = findset(b);
par[a] = b;
}
void gobig() {
for (int i = 1; i <= n; i++) {
if (dep[i] % 60 != 0)
label[i] = dep[i] % 60; //easy way to do it
else label[i] = 60;
}
//this is all we need
}
void preorder(int u, int p) {
desired[u] = true;
seen++;
for (int v : adj[u]) {
if (seen == 60 || v == p) continue;
preorder(v, u);
}
}
void postorder(int u, int p) {
for (int v : adj[u]) {
if (v == p) continue;
if (desired[v]) {
postorder(v, u);
}
}
label[u] = ++seen;
}
void dfs2(int u, int p, int dl) {
if (!desired[u]) {
label[u] = dep[u] = dl;
}
else dl = dep[u];
for (int v : adj[u]) {
if (v == p) continue;
dfs2(v, u, dl);
}
}
void gosmall() {
seen = 0;
preorder(1, -1);
seen = 0;
postorder(1, -1);
dfs2(1, -1, 0);
}
#ifdef LOCAL
void MessageBoard(int attr, int msg) {
}
#endif
void constructLabels() {
for (int i = 1; i <= n; i++) {
if (x2 & (1LL << (label[i]-1))) {
MessageBoard(i-1, 1);
}
else MessageBoard(i-1, 0);
}
}
void Joi(int N, int M, int A[], int B[], long long X, int T) {
n = N;
m = M;
x2 = X;
for (int i = 1; i <= n; i++) {
par[i] = i;
}
for (int i = 0; i < m; i++) {
int v1 = A[i]+1;
int v2 = B[i]+1;
if (findset(v1) != findset(v2)) {
unionset(v1, v2);
adj[v1].push_back(v2);
adj[v2].push_back(v1);
}
}
dfs(1, -1); //set up the trees
if (maxd >= 60) {
gobig();
}
else {
gosmall();
// assert(false);
}
constructLabels(); //specific to Joi version
}
#ifdef LOCAL
int main() {
}
#endif
//run the same labelling scheme
//label each index according to which bit it stores
//difference is that the first guy sets the corresponding bit,
// the second guy has to figure it out.
#include <bits/stdc++.h>
#include "Ioi.h"
using namespace std;
#define ll long long
// #define LOCAL
const int maxni = 100010;
int bit[62];
vector<vector<int>> adj(maxni);
int n;
int m;
int par[maxni];
int dep[maxni];
int label[maxni]; //which bit i correspond to
int seen = 0;
bool alseen[maxni]; //already seen this label
int pc[maxni];
int furthestdown[maxni];
int bestnode[maxni];
bool desired[maxni];
int maxd = 0;
int loc; //initial location
int val; //value at attraction p
#ifdef LOCAL
int Move(int val) {
return 1;
}
#endif
int move(int loc) {
// cout << "going to " << loc << endl;
return Move(loc-1);
}
void dfs(int u, int p) {
// cout << "dfs: : " << u << " " << p << endl;
dep[u] = p == - 1 ? 1 : dep[p]+1;
pc[u] = p;
maxd = max(maxd, dep[u]);
furthestdown[u] = dep[u];
bestnode[u] = 0;
for (int v : adj[u]) {
if (v == p) continue;
dfs(v, u);
if (furthestdown[v] > furthestdown[u]) {
furthestdown[u] = furthestdown[v];
bestnode[u] = v;
}
}
}
int findset(int u) {
if (par[u] == u) return u;
return par[u] = findset(par[u]);
}
void unionset(int a, int b) {
a = findset(a);
b = findset(b);
par[a] = b;
}
void gobig() {
for (int i = 1; i <= n; i++) {
if (dep[i] % 60 != 0)
label[i] = dep[i] % 60; //easy way to do it
else label[i] = 60;
}
//this is all we need
}
void preorder(int u, int p) {
desired[u] = true;
seen++;
for (int v : adj[u]) {
if (seen == 60 || v == p) continue;
preorder(v, u);
}
}
void postorder(int u, int p) {
for (int v : adj[u]) {
if (v == p) continue;
if (desired[v]) {
postorder(v, u);
}
}
label[u] = ++seen;
}
void dfs2(int u, int p, int dl) {
if (!desired[u]) {
label[u] = dep[u] = dl;
}
else dl = dep[u];
for (int v : adj[u]) {
if (v == p) continue;
dfs2(v, u, dl);
}
}
void gosmall() {
seen = 0;
preorder(1, -1);
seen = 0;
postorder(1, -1);
dfs2(1, -1, 0);
}
void ansbig() {
// cout << "DOING BIG" << endl;
//this is easy
//remember loc is the initial place
bit[label[loc]] = val;
int quer = 0;
while (loc != 1 && quer < 61) {
// cout << "cur loc " << loc << " : " << pc[loc] << endl;
loc = pc[loc];
bit[label[loc]] = move(loc);
quer++;
}
if (quer < 61) {
//keep going down while I can
while (dep[loc] < 60) {
loc = bestnode[loc];
bit[label[loc]] = move(loc);
}
}
}
void anssmall() {
// cout << "DOING SMALL" << endl;
bit[label[loc]] = val;
alseen[label[loc]] = true;
while (!desired[loc]) {
// cout << "trying to go up from " << loc << " : " << pc[loc] << endl;
loc = pc[loc];
bit[label[loc]] = move(loc);
if (!desired[loc]) alseen[label[loc]] = true;
}
while (true) {
if (alseen[loc]) {
loc = pc[loc];
if (loc == -1) break;
bit[label[loc]] = move(loc);
}
else {
bool fin = false;
for (int v : adj[loc]) {
if (v == pc[loc]) continue;
if (!alseen[v]) {
loc = v;
bit[label[loc]] = move(loc);
fin = true;
alseen[v] = true;
break;
}
// alseen[loc] = true;
}
if (!fin) alseen[loc] = true;
}
}
}
ll constructans() {
ll ans = 0LL;
for (int i = 60; i >= 1; i--) {
ans = (ans*2LL) + bit[i];
}
return ans;
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
//run stuff and then do connstruct ans
n = N;
m = M;
loc = P;
loc++;
val = V;
for (int i = 1; i <= n; i++) {
par[i] = i;
}
for (int i = 0; i < m; i++) {
++A[i];
++B[i];
// cout << i << ": looking at " << A[i] << " " << B[i] << endl;
if (findset(A[i]) != findset(B[i])) {
// cout << "unioned " << A[i] << " to " << B[i] << endl;
// cout << "UNIONING A SET" << endl;
unionset(A[i], B[i]);
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
}
dfs(1, -1); //set up the trees
if (maxd >= 60) {
gobig();
ansbig();
}
else {
gosmall();
// cout << "asddhfasldkhhldghk;gsk" << endl;
anssmall();
}
return constructans();
}
#ifdef LOCAL
int main() {
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
3296 KB |
Wrong Answer [7] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
6980 KB |
Output is correct |
| 2 |
Correct |
34 ms |
8376 KB |
Output is correct |
| 3 |
Correct |
31 ms |
8484 KB |
Output is correct |
| 4 |
Incorrect |
25 ms |
8592 KB |
Wrong Answer [7] |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8592 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8592 KB |
Output is correct |
| 3 |
Correct |
6 ms |
8592 KB |
Output is correct |
| 4 |
Correct |
8 ms |
8592 KB |
Output is correct |
| 5 |
Correct |
11 ms |
8592 KB |
Output is correct |
| 6 |
Correct |
8 ms |
8592 KB |
Output is correct |
| 7 |
Correct |
7 ms |
8592 KB |
Output is correct |
| 8 |
Correct |
9 ms |
8592 KB |
Output is correct |
| 9 |
Correct |
18 ms |
8964 KB |
Output is correct |
| 10 |
Correct |
19 ms |
9336 KB |
Output is correct |
| 11 |
Correct |
17 ms |
9336 KB |
Output is correct |
| 12 |
Correct |
6 ms |
9336 KB |
Output is correct |
| 13 |
Correct |
7 ms |
9336 KB |
Output is correct |
| 14 |
Correct |
8 ms |
9336 KB |
Output is correct |
| 15 |
Correct |
7 ms |
9336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
9336 KB |
Output is correct |
| 2 |
Correct |
34 ms |
9336 KB |
Output is correct |
| 3 |
Correct |
31 ms |
9336 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
9336 KB |
Wrong Answer [7] |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
9336 KB |
Output is correct |
| 2 |
Correct |
32 ms |
9336 KB |
Output is correct |
| 3 |
Correct |
31 ms |
9336 KB |
Output is correct |
| 4 |
Incorrect |
20 ms |
9336 KB |
Wrong Answer [7] |
| 5 |
Halted |
0 ms |
0 KB |
- |
