제출 #829434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
829434		burythelightdeepwithin	Amusement Park (JOI17_amusement_park)	C++14	0 / 100	11 ms	3652 KiB

Joi

#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);
    }
}

Ioi

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17