oj.uz

Submission #27125

# Submission time Handle Problem Language Result Execution time Memory
27125 2017-07-09T11:57:16 Z zoomswk Amusement Park (JOI17_amusement_park) C++14
0 / 100
 3000 ms 42396 KB 
#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);
}



#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 30044 KB Output is correct
2 Incorrect 6 ms 30044 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 42396 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 30044 KB Output is correct
2 Correct 0 ms 30044 KB Output is correct
3 Incorrect 3 ms 30044 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 42364 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 42012 KB Execution timed out
2 Halted 0 ms 0 KB -