#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(u, v);
}
}
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++) {
++A[i];
++B[i];
if (findset(A[i]) != findset(B[i])) {
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();
}
else {
gosmall();
}
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-1 << endl;
return Move(loc-1);
}
void dfs(int u, int p) {
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(u, v);
}
}
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() {
//this is easy
//remember loc is the initial place
bit[label[loc]] = val;
int quer = 0;
while (loc != 1 && quer < 61) {
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() {
bit[label[loc]] = val;
alseen[label[loc]] = true;
while (!desired[loc]) {
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 {
for (int v : adj[loc]) {
if (v == pc[loc]) continue;
if (!alseen[v]) {
loc = v;
bit[label[loc]] = move(loc);
break;
}
}
}
}
}
ll constructans() {
ll ans = 0LL;
for (int i = 60; i >= 1; i--) {
ans = (ans*2LL) + bit[i];
}
}
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;
val = V;
for (int i = 1; i <= n; i++) {
par[i] = i;
}
for (int i = 0; i < m; i++) {
++A[i];
++B[i];
if (findset(A[i]) != findset(B[i])) {
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();
anssmall();
}
return constructans();
}
#ifdef LOCAL
int main() {
}
#endif
Compilation message
Ioi.cpp: In function 'long long int constructans()':
Ioi.cpp:167:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3107 ms |
393216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
30 ms |
786432 KB |
Do not print anything on standard output. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
786432 KB |
Do not print anything on standard output. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
33 ms |
786432 KB |
Do not print anything on standard output. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
30 ms |
786432 KB |
Do not print anything on standard output. |
| 2 |
Halted |
0 ms |
0 KB |
- |
