Submission #1215021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215021		vanea	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2093 ms	22248 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mxN = 1e5+10;

vector<int> adj[mxN];
set<array<int, 2>> idx[mxN], dist[mxN];
int in_deg[mxN], in_deg1[mxN], d[mxN];
bool bad[mxN], vis[mxN];

int main()
{
    //freopen("02-19.txt", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        ++in_deg[b]; in_deg1[b] = in_deg[b];
    }
    int block_size = 100;
    queue<int> qe;
    for(int i = 1; i <= n; i++) {
        dist[i].insert({0, i});
        idx[i].insert({i, 0});
    }
    for(int i = 1; i <= n; i++) {
        if(in_deg[i] == 0) {
            qe.push(i);
        }
    }
    int cnt = 0;
    while(!qe.empty()) {
        int node = qe.front();
        qe.pop();
        ++cnt;
        vis[node] = true;
        for(auto it : adj[node]) {
            auto it1 = dist[node].begin();
            while(dist[it].size() < block_size && it1 != dist[node].end()) {
                array<int, 2> a = *it1; a[0]++;
                auto it2 = idx[it].lower_bound({a[1], 0});
                if(it2 != idx[it].end() && (*it2)[0] == a[1]) {
                    array<int, 2> a1 = *it2;
                    if(a1[1] < a[0]) {
                        idx[it].erase(a1);
                        dist[it].erase({a1[1], a1[0]});
                    }
                    else {
                        ++it1;
                        continue;
                    }
                }
                dist[it].insert(a);
                idx[it].insert({a[1], a[0]});
                ++it1;
            }
            while(it1 != dist[node].end()) {
                auto curr = dist[it].begin();
                array<int, 2> a = *curr, b = *it1; b[0]++;
                ++it1;
                array<int, 2> a1 = {a[1], a[0]}, b1 = {b[1], 0};
                auto it2 = idx[it].lower_bound(b1);
                if(it2 != idx[it].end() && (*it2)[0] == b[1]) {
                    if((*it2)[1] < b[0]) {
                        idx[it].erase(it2);
                        dist[it].erase({(*it2)[1], (*it2)[0]});
                        dist[it].insert(b);
                        b1[1] = b[0];
                        idx[it].insert(b1);
                    }
                    continue;
                }
                b1[1] = b[0];
                if(a[0] < b[0]) {
                    dist[it].erase(a);
                    dist[it].insert(b);
                    idx[it].erase(a1);
                    idx[it].insert(b1);
                }
            }
            --in_deg[it];
            if(in_deg[it] == 0) qe.push(it);
        }
    }
    while(q--) {
        int t, y;
        cin >> t >> y;
        vector<int> now(y);
        for(int i = 0; i < y; i++) cin >> now[i];
        if(y <= block_size-3) {
            vector<array<int, 2>> removed;
            for(auto it : now) {
                auto it1 = idx[t].lower_bound({it, 0});
                if(it1 != idx[t].end() && (*it1)[0] == it) {
                    removed.push_back(*it1);
                    idx[t].erase(it1);
                    dist[t].erase({(*it1)[1], (*it1)[0]});
                }
            }
            if(dist[t].empty()) {
                cout << -1 << '\n';
            }
            else {
                auto ans = dist[t].end(); --ans;
                cout << (*ans)[0] << '\n';
            }
            for(auto it : removed) {
                dist[t].insert({it[1], it[0]});
                idx[t].insert(it);
            }
        }
        else {
            for(int i = 1; i <= n; i++) {
                in_deg[i] = in_deg1[i];
                d[i] = 0;
                if(in_deg[i] == 0) {
                    qe.push(i);
                }
            }
            for(auto it : now) bad[it] = true;
            while(!qe.empty()) {
                int node = qe.front();
                qe.pop();
                for(auto it : adj[node]) {
                    --in_deg[it];
                    if(!bad[node]) {
                        d[it] = max(d[it], d[node]+1);
                    }
                    else {
                        if(d[node] != 0) d[it] = max(d[it], d[node]+1);
                    }
                    if(in_deg[it] == 0) qe.push(it);
                }
            }
            if(bad[t] && d[t] == 0) cout << -1 << '\n';
            else cout << d[t] << '\n';
            for(auto it : now) bad[it] = false;
        }
    }
}

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