oj.uz

Submission #829434

# Submission time Handle Problem Language Result Execution time Memory
829434 2023-08-18T10:37:46 Z burythelightdeepwithin Amusement Park (JOI17_amusement_park) C++14
0 / 100
 11 ms 3652 KB 
#include <bits/stdc++.h>
#include "Joi.h"

using namespace std;

const int N = 1e4+3;
vector <int> adj[N], tree[N];
int h[N], vs[N], par[N], mx[N], in[N];
int root = N;
bool able = false;
string s;

string dtb(long long n){
    string res;
    while(n > 0){
        int a = n%2;
        res += (a+'0');
        n /= 2;
    }
    while ((int)res.size() < 60){
        res += '0';
    }
    return res;
}

void dfs(int u){
    vs[u] = 1;
    mx[u] = h[u];
    for (auto v: adj[u]){
        if (!vs[v]){
            h[v] = h[u] + 1;
            par[v] = u;
            tree[u].push_back(v);
            //tree[v].push_back(u);
            dfs(v);
            mx[u] = max(mx[u], mx[v]);
        }
    }
    if (mx[u] >= 59){
        able = true;
        in[u] = 1;
    }
}

void process(int u, int d){
    MessageBoard(u, s[d%60] - '0');
    for (auto v: tree[u]){
        par[v] = u;
        process(v, d+1);
    }
}

void Joi(int N, int M, int A[], int B[], long long X, int T){
    for (int i = 0; i < M; i++){
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    for (int i = 0; i < N; i++){
        if (able){
            break;
        }
        root = i;
        for (int j = 0; j < N; j++){
            vs[j] = 0;
            h[j] = 0;
            par[j] = 0;
            tree[j].clear();
        }
        dtb(X);
        dfs(root);
        process(root, 0);
    }
}

#include <bits/stdc++.h>
#include "Ioi.h"

using namespace std;

const int N = 1e4+3;
vector <int> adj[N], tree[N];
int h[N], vs[N], par[N], mx[N], in[N];
int root = N;
bool able = false, backwards = 0;
long long ans = 0;
string s;

void btd(string s){
    int base = 1;
    for (int i = 0; i < (int)s.size(); i++){
        ans += base*(s[i] - '0');
        base *= 2;
    }
}

void dfs(int u){
    vs[u] = 1;
    mx[u] = h[u];
    for (auto v: adj[u]){
        if (!vs[v]){
            h[v] = h[u] + 1;
            par[v] = u;
            tree[u].push_back(v);
            //tree[v].push_back(u);
            dfs(v);
            mx[u] = max(mx[u], mx[v]);
        }
    }
    if (mx[u] >= 59){
        able = true;
        in[u] = 1;
    }
}

long long Ioi (int N, int M, int A[], int B[], int P, int V, int T){
    for (int i = 0; i < M; i++){
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    for (int i = 0; i < N; i++){
        if (able){
            break;
        }
        root = i;
        for (int j = 0; j < N; j++){
            vs[j] = 0;
            h[j] = 0;
            par[j] = 0;
            tree[j].clear();
        }
        dfs(root);
    }
    int now = V;
    while(!in[now]){
        Move(par[now]);
    }
    while(h[now] % 60 != 0){
        Move(par[now]);
    }
    if (h[now] + 59 > mx[now]){
        backwards = 1;
    }
    if (backwards){
        for (int i = 1; i <= 60; i++){
            s += (char)(Move(par[now])+'0');
        }
        reverse(s.begin(), s.end());
    } else {
        for (auto v: tree[now]){
            if (in[v]){
                Move(v);
                break;
            }
        }
        s += Move(par[now]);
        for (int i = 1; i < 60; i++){
            for (auto v: tree[now]){
                if (in[v]){
                    s += (char)(Move(v) + '0');
                    break;
                }
            }
        }
    }
    btd(s);
    return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1540 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 3564 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1544 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3652 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3572 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -