Submission #711025

#	Time	Username	Problem	Language	Result	Execution time	Memory
711025		thimote75	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2054 ms	6176 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

#define idata vector<int>
#define igrid vector<idata>
#define di pair<int, int>

int nbNodes, nbRoads, nbQuery;
igrid roads;

const int BLOCK_SIZE = 400;

di delta[BLOCK_SIZE];
set<int> sdd_reverse;

struct VBO {
    di sdd[BLOCK_SIZE];

    void insert (int node, int depth) {
        for (int i = 0; i < BLOCK_SIZE; i ++)
            sdd[i] = di(-1, -1);
        
        sdd[0] = di(depth, node);
        sdd_reverse.insert(node);
    }
    int query (set<int> &disabled) {
        for (int i = 0; i < BLOCK_SIZE; i ++) {
            di data = sdd[i];
            if (data.first == -1) continue ;
            if (disabled.find(data.second) != disabled.end()) continue ;

            return data.first;
        }

        return -1;
    }

    di next (int index) {
        di v = sdd[index];
        v.first ++;
        return v;
    }
    void merge (VBO &other) {
        int left  = 0;
        int right = 0;

        sdd_reverse.clear();

        for (int i = 0; i < BLOCK_SIZE; i ++)
            delta[i] = di(-1, -1);

        int cursor = 0;
        while (cursor < BLOCK_SIZE
           && ((left  < BLOCK_SIZE && sdd[left].first != -1) 
            || (right < BLOCK_SIZE && other.sdd[right].first != -1))) {
            bool lv = (left  < BLOCK_SIZE && sdd[left].first != -1);
            bool rv = (right < BLOCK_SIZE && other.sdd[right].first != -1);

            di value;
            if (lv && rv) {
                if (sdd[left] > other.next(right)) {
                    value = sdd[left ++];
                } else value = other.next(right ++);
            } else {
                if (lv) value = sdd[left ++];
                else value = other.next(right ++);
            }

            if (sdd_reverse.find(value.second) != sdd_reverse.end()) continue ;
            delta[cursor] = value;
            sdd_reverse.insert(value.second);
            cursor ++;
        }

        for (int i = 0; i < BLOCK_SIZE; i ++)
            sdd[i] = delta[i];
    }
};

vector<VBO> vbos;
vector<int> bfs_v;
vector<int> dfs_v;
vector<int> visited;
int stage = 1;

void dfs (int node) {
    if (visited[node] == stage) return ;
    visited[node] = stage;

    vbos[node].insert(node, 0);

    for (int prev : roads[node]) {
        dfs(prev);

        vbos[node].merge(vbos[prev]);
    }
}
void _c_dfs (int node) {
    if (visited[node] == stage) return ;
    visited[node] = stage;
    for (int prev : roads[node]) {
        dfs_v[prev] ++;

        _c_dfs(prev);
    }
}
int _compute (int start, set<int> &disabled) {
    queue<int> nodes;
    nodes.push(start);

    fill(dfs_v.begin(), dfs_v.end(), 0);
    _c_dfs(start);
    stage ++;

    fill(bfs_v.begin(), bfs_v.end(), -1);
    bfs_v[start] = 0;

    int answer = -1;
    while (nodes.size() != 0) {
        int curr = nodes.front();
        nodes.pop();
        
        if (disabled.find(curr) == disabled.end())
            answer = max(answer, bfs_v[curr]);

        for (int prev : roads[curr]) {
            dfs_v[prev] --;
            if (dfs_v[prev] != 0) continue ;
        
            bfs_v[prev] = bfs_v[curr] + 1;
            nodes.push(prev);
        }
    }

    return answer;
}
int compute (int node, set<int> &disabled) {
    if (disabled.size() <= BLOCK_SIZE)
        return vbos[node].query(disabled);
    
    return _compute(node, disabled);
}

int main () {
    cin >> nbNodes >> nbRoads >> nbQuery;
    vbos .resize(nbNodes);
    roads.resize(nbNodes);
    visited.resize(nbNodes);
    dfs_v.resize(nbNodes);
    bfs_v.resize(nbNodes);

    for (int idRoad = 0; idRoad < nbRoads; idRoad ++) {
        int a, b;
        cin >> a >> b;

        a --; b --;
        roads[b].push_back(a);
    }

    for (int idNode = 0; idNode < nbNodes; idNode ++)
        dfs(idNode);
    stage ++;

    for (int idQuery = 0; idQuery < nbQuery; idQuery ++) {
        int target, dCount;
        cin >> target >> dCount;
        target --;

        set<int> disabled;
        for (int idD = 0; idD < dCount; idD ++) {
            int vd;
            cin >> vd;
            vd --;

            disabled.insert(vd);
        }

        cout << compute(target, disabled) << endl;
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86