Submission #27141

#	Time	Username	Problem	Language	Result	Execution time	Memory
27141		zoomswk	Amusement Park (JOI17_amusement_park)	C++14	18 / 100	2929 ms	31632 KiB

Joi

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

namespace GUI{

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

queue<pair<int, int>> q;

void init(int pos){
    if(done_cnt == 60) return;
    if(id[pos]) return;
    id[pos] = ++done_cnt;
    if(done_cnt == 60) return;
    for(pair<int, int> v : way[pos]) if(!id[v.first] && done_cnt < 60) use[v.second] = 1, init(v.first);
    return;
}

void dfs(int pos, int from){
    if(id[pos]) return;
    for(int i=0; i<10000; i++) dist[i] = 1e9;
    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(pair<int, int> x : way[pos]) if(use[x.second]) q.push({d+1, x.first});
    }
    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(pair<int, int> v : way[pos]){
        if(id[v.first]) continue;
        use[v.second] = 1;
        dfs(v.first, 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], i}), way[B[i]].push_back({A[i], 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(pair<int, int> v : way[i]) use[v.second] = 1, dfs(v.first, 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<pair<int, int>> way[10005];
int use[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(pair<int, int> v : way[pos]) if(!id[v.first] && done_cnt < 60) use[v.second] = 1, init(v.first);
    return;
}

queue<pair<int, int>> q;

void dfs(int pos, int from){
    if(id[pos]) return;
    for(int i=0; i<10000; i++) dist[i] = 1e9;
    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(pair<int, int> x : way[pos]) if(use[x.second]) q.push({d+1, x.first});
    }
    int mxdist=0, mxer=-1;
    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;
            }
        }
    }
    if(mxer == -1){ printf("!!!\n"); }
    take[pos][mxer] = 0;
    take[pos][pos] = 1;
    id[pos] = id[mxer];
    for(pair<int, int> v : way[pos]){
        if(id[v.first]) continue;
        use[v.second] = 1;
        dfs(v.first, pos);
    }
    return;
}

int res[65];

int vs[10005];

int gbP;

void get_ans(int pos){
    vs[pos] = 1;
    //printf("VS %d\n", pos);
    for(pair<int, int> v : way[pos]){
        //printf("TRY %d\n", v.first);
        if((!take[gbP][v.first]) || vs[v.first]) continue;
        int x = Move(v.first);
        res[id[v.first]] = x;
        get_ans(v.first);
        Move(pos);
    }
    return;
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
    gbP = P;
    for(int i=0; i<M; i++) way[A[i]].push_back({B[i], i}), way[B[i]].push_back({A[i], 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(pair<int, int> v : way[i]) use[v.second] = 1, dfs(v.first, 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: 8 / 8
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17