oj.uz

Submission #829588

# Submission time Handle Problem Language Result Execution time Memory
829588 2023-08-18T13:07:12 Z burythelightdeepwithin Amusement Park (JOI17_amusement_park) C++14
0 / 100
 22 ms 5660 KB 
#include <bits/stdc++.h>
#include "Joi.h"

using namespace std;

const int maxN = 1e4+3;
vector <int> adj[maxN], tree[maxN];
int h[maxN], vs[maxN], par[maxN], mx[maxN], in[maxN];
int root = maxN;
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){
    s = dtb(X);
    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;
            in[j] = 0;
            tree[j].clear();
        }
        dfs(root);
        if (able){
            process(root, 0);
        }
    }
}

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

using namespace std;

const int maxN = 1e4+3;
vector <int> adj[maxN], tree[maxN];
int h[maxN], vs[maxN], par[maxN], mx[maxN], in[maxN];
int root = maxN;
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;
            in[j] = 0;
            tree[j].clear();
        }
        dfs(root);
    }
    int now = V;
    while(!in[now]){
        Move(par[now]);
        now = par[now];
    }
    while(h[now] % 60 != 0){
        Move(par[now]);
        now = par[now];
    }
    if (h[now] + 59 > mx[now]){
        backwards = 1;
    }
    if (backwards){
        for (int i = 1; i <= 60; i++){
            s += (Move(par[now])+'0');
            now = par[now];
        }
        reverse(s.begin(), s.end());
    } else {
        for (int i = 1; i <= 60; i++){
            for (auto v: tree[now]){
                if (in[v]){
                    now = v;
                    break;
                }
            }
        }
        for (int i = 1; i <= 60; i++){
            s += (Move(par[now])+'0');
            now = par[now];
        }
        reverse(s.begin(), s.end());
    }
    btd(s);
    return ans;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 5660 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 5504 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 5616 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -