제출 #27125

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

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

namespace GUI{

vector<int> way[10005];
int done[10005];
int done_cnt;
int id[10005];
bitset<10000> take[10005];
int dist[10005];

void init(int pos){
    if(done_cnt == 60) return;
    if(id[pos]) return;
    id[pos] = ++done_cnt;
    if(done_cnt == 60) return;
    for(int v : way[pos]) init(v);
    return;
}

void dfs(int pos, int from){
    if(id[pos]) return;
    for(int i=0; i<10000; i++) dist[i] = 1e9;
    queue<pair<int, int>> q;
    q.push({0, pos});
    while(!q.empty()){
        int d = q.front().first, pos = q.front().second;
        q.pop();
        if(d >= dist[pos]) continue;
        dist[pos] = d;
        for(int x : way[pos]) q.push({d+1, x});
    }
    int mxdist=0, mxer=0;
    for(int i=0; i<10000; i++){
        take[pos][i] = take[from][i];
        if(take[pos][i]){
            if(dist[i] > mxdist){
                mxdist = dist[i];
                mxer = i;
            }
        }
    }
    take[pos][mxer] = 0;
    take[pos][pos] = 1;
    id[pos] = id[mxer];
    for(int v : way[pos]) dfs(v, pos);
    return;
}

int bit[65];

void Joi(int N, int M, int A[], int B[], long long X, int T) {
    for(int i=0; i<M; i++) way[A[i]].push_back(B[i]), way[B[i]].push_back(A[i]);
    init(0);
    for(int i=0; i<N; i++){
        if(id[i]){
            for(int j=0; j<N; j++) if(id[j]) take[i][j] = 1;
        }
    }
    for(int i=0; i<N; i++){
        if(take[0][i]){
            for(int v : way[i]) dfs(v, i);
        }
    }
    for(int i=1; i<=60; i++){
        if(X&1) bit[i] = 1;
        else bit[i] = 0;
        X >>= 1;
    }
    for(int i=0; i<N; i++) if(bit[id[i]] != 0 && bit[id[i]] != 1){ exit(1); }
    for(int i=0; i<N; i++) MessageBoard(i, bit[id[i]]);
    return;
}


}

void Joi(int N, int M, int A[], int B[], long long X, int T){
    GUI::Joi(N, M, A, B, X, T);
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> way[10005];
int done[10005];
int done_cnt;
int id[10005];
bitset<10000> take[10005];
int dist[10005];

void init(int pos){
    if(done_cnt == 60) return;
    if(id[pos]) return;
    id[pos] = ++done_cnt;
    if(done_cnt == 60) return;
    for(int v : way[pos]) init(v);
    return;
}

void dfs(int pos, int from){
    if(id[pos]) return;
    for(int i=0; i<10000; i++) dist[i] = 1e9;
    queue<pair<int, int>> q;
    q.push({0, pos});
    while(!q.empty()){
        int d = q.front().first, pos = q.front().second;
        q.pop();
        if(d >= dist[pos]) continue;
        dist[pos] = d;
        for(int x : way[pos]) q.push({d+1, x});
    }
    int mxdist=0, mxer=0;
    for(int i=0; i<10000; i++){
        take[pos][i] = take[from][i];
        if(take[pos][i]){
            if(dist[i] > mxdist){
                mxdist = dist[i];
                mxer = i;
            }
        }
    }
    take[pos][mxer] = 0;
    take[pos][pos] = 1;
    id[pos] = id[mxer];
    for(int v : way[pos]) dfs(v, pos);
    return;
}

int res[65];

int vs[10005];

int gbV;

void get_ans(int pos){
    vs[pos] = 1;
    for(int v : way[pos]){
        if((!take[gbV][v]) || vs[v]) continue;
        int x = Move(v);
        res[id[v]] = x;
        get_ans(v);
        Move(pos);
    }
    return;
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    gbV = V;
    for(int i=0; i<M; i++) way[A[i]].push_back(B[i]), way[B[i]].push_back(A[i]);
    init(0);
    for(int i=0; i<N; i++){
        if(id[i]){
            for(int j=0; j<N; j++) if(id[j]) take[i][j] = 1;
        }
    }
    for(int i=0; i<N; i++){
        if(take[0][i]) for(int v : way[i]) dfs(v, i);
    }
    res[id[P]] = V;
    get_ans(P);
    long long X = 0;
    for(int i=60; i>=1; i--){
        X <<= 1;
        X += res[i];
    }
    return X;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17