oj.uz

Submission #710836

# Submission time Handle Problem Language Result Execution time Memory
710836 2023-03-15T22:00:33 Z thimote75 Bitaro’s Party (JOI18_bitaro) C++14
7 / 100
 1827 ms 524288 KB 
#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;

struct VBO {
    unordered_map<int, int> sdd_reverse;
    set<di, greater<>> sdd;

    void insert (int node, int depth) {
        if (sdd_reverse.find(node) != sdd_reverse.end()) {
            int max_depth = (*sdd_reverse.find(node)).second;
            if (max_depth >= depth) return ;

            sdd_reverse.erase(node);
            sdd.erase(di(max_depth, node));
        }
        
        sdd_reverse.insert(di(node, depth));
        sdd.insert(di(depth, node));

        if (sdd.size() <= BLOCK_SIZE) return ;
        auto it = sdd.end();
        it --;
        
        int rnode  = (*it).second;
        int rdepth = (*it).first;

        sdd_reverse.erase(rnode);
        sdd.erase(di(rdepth, rnode));
    }
    int query (set<int> &disabled) {
        for (di data : sdd) {
            if (disabled.find(data.second) != disabled.end()) continue ;

            return data.first;
        }

        return -1;
    }

    void merge (VBO &other) {
        for (di data : other.sdd)
            this->insert(data.second, data.first + 1);
    }
};

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

void dfs (int node) {
    vbos[node].insert(node, 0);

    for (int prev : roads[node]) {
        if (vbos[node].sdd.size() == 0)
            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);

    dfs_v.clear();
    dfs_v.resize(nbNodes, 0);
    _c_dfs(start);
    stage ++;

    bfs_v.clear();
    bfs_v.resize(nbNodes, -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);

    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 ++) {
        if (vbos[idNode].sdd.size() != 0) continue ;

        dfs(idNode);
    }

    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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 12 ms 3796 KB Output is correct
6 Correct 14 ms 4052 KB Output is correct
7 Correct 12 ms 3704 KB Output is correct
8 Correct 83 ms 28936 KB Output is correct
9 Correct 95 ms 29012 KB Output is correct
10 Correct 98 ms 28944 KB Output is correct
11 Correct 81 ms 24788 KB Output is correct
12 Correct 34 ms 10452 KB Output is correct
13 Correct 76 ms 23580 KB Output is correct
14 Correct 67 ms 17228 KB Output is correct
15 Correct 41 ms 8068 KB Output is correct
16 Correct 78 ms 16692 KB Output is correct
17 Correct 67 ms 18800 KB Output is correct
18 Correct 34 ms 9496 KB Output is correct
19 Correct 68 ms 18764 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 12 ms 3796 KB Output is correct
6 Correct 14 ms 4052 KB Output is correct
7 Correct 12 ms 3704 KB Output is correct
8 Correct 83 ms 28936 KB Output is correct
9 Correct 95 ms 29012 KB Output is correct
10 Correct 98 ms 28944 KB Output is correct
11 Correct 81 ms 24788 KB Output is correct
12 Correct 34 ms 10452 KB Output is correct
13 Correct 76 ms 23580 KB Output is correct
14 Correct 67 ms 17228 KB Output is correct
15 Correct 41 ms 8068 KB Output is correct
16 Correct 78 ms 16692 KB Output is correct
17 Correct 67 ms 18800 KB Output is correct
18 Correct 34 ms 9496 KB Output is correct
19 Correct 68 ms 18764 KB Output is correct
20 Correct 1358 ms 29980 KB Output is correct
21 Correct 1146 ms 31556 KB Output is correct
22 Correct 1537 ms 31504 KB Output is correct
23 Correct 1827 ms 31504 KB Output is correct
24 Runtime error 1777 ms 524288 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 12 ms 3796 KB Output is correct
6 Correct 14 ms 4052 KB Output is correct
7 Correct 12 ms 3704 KB Output is correct
8 Correct 83 ms 28936 KB Output is correct
9 Correct 95 ms 29012 KB Output is correct
10 Correct 98 ms 28944 KB Output is correct
11 Correct 81 ms 24788 KB Output is correct
12 Correct 34 ms 10452 KB Output is correct
13 Correct 76 ms 23580 KB Output is correct
14 Correct 67 ms 17228 KB Output is correct
15 Correct 41 ms 8068 KB Output is correct
16 Correct 78 ms 16692 KB Output is correct
17 Correct 67 ms 18800 KB Output is correct
18 Correct 34 ms 9496 KB Output is correct
19 Correct 68 ms 18764 KB Output is correct
20 Correct 1358 ms 29980 KB Output is correct
21 Correct 1146 ms 31556 KB Output is correct
22 Correct 1537 ms 31504 KB Output is correct
23 Correct 1827 ms 31504 KB Output is correct
24 Runtime error 1777 ms 524288 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -