Submission #750627

#	Time	Username	Problem	Language	Result	Execution time	Memory
750627		Shreyan_Paliwal	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1104 ms	422300 KiB

bitaro

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

const int maxn = 100000;
const int SQRTN = 330;

struct Party {
    int nd;
    vector<int> not_allowed;
};

int n, m, q;
vector<int> adj[maxn];
vector<int> rev[maxn];
Party parties[maxn];

vector<pair<int,int>> track[maxn]; // tracks SQRTN best
int vis[maxn]; // when merging, tracks which ones are done

int dp[maxn]; // when naive, tracks best for each one
int dpvis[maxn]; // tracks which parties not to include

int apply_naive(int party) {
    int nd = parties[party].nd;
    for (auto i : parties[party].not_allowed) dpvis[i] = true;

    for (int i = 0; i <= nd; i++) {
        dp[i] = (dpvis[i] ? -1 : 0);
        for (auto j : rev[i])
            dp[i] = max(dp[i], dp[j] + (dp[j] != -1));
    }

    for (auto i : parties[party].not_allowed) dpvis[i] = false;
    return dp[nd];
}

void unite(int i, int j, vector<pair<int,int>>& fin) {
    int icnt = 0, jcnt = 0;
    while (fin.size() < SQRTN && (icnt < (int)track[i].size() || jcnt < (int)track[j].size())) {
        if (jcnt == (int)track[j].size() || (i < (int)track[i].size() && track[i][icnt].first > track[j][jcnt].first)) {
            vis[track[i][icnt].second] = 1;
            fin.push_back(track[i][icnt]); icnt++;
        } else {
            vis[track[j][jcnt].second] = 1;
            fin.push_back(track[j][jcnt]); jcnt++;
            fin.back().first++;
        }

        while (icnt < (int)track[i].size() && vis[track[i][icnt].second]) icnt++;
        while (jcnt < (int)track[j].size() && vis[track[j][jcnt].second]) jcnt++;
    }
    for (auto x : fin) vis[x.second] = 0;
}

void init_short() {
    track[0].push_back({0, 0});

    for (int i = 1; i < n; i++) {
        track[i].push_back({0, i});
        for (auto j : rev[i]) {
            // unite track[i] with track[j]
            vector<pair<int,int>> fin;
            unite(i, j, fin);
            swap(track[i], fin);
        }
    }
}

int apply_short(int party) {
    int nd = parties[party].nd;
    for (auto i : parties[party].not_allowed) dpvis[i] = true;

    int ans = -1;
    for (auto i : track[nd])
        if (!dpvis[i.second]) {
            ans = i.first;
            break;
        }

    for (auto i : parties[party].not_allowed) dpvis[i] = false;

    return ans;
}

int main() {
    // freopen("main.in", "r", stdin);

    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b; a--, b--;
        adj[a].push_back(b);
        rev[b].push_back(a);
    }
    for (int i = 0; i < q; i++) {
        cin >> parties[i].nd; parties[i].nd--;
        int x; cin >> x;
        while (x--) {
            int b; cin >> b; b--;
            parties[i].not_allowed.push_back(b);
        }
    }

    init_short();

    for (int i = 0; i < q; i++) {
        if (parties[i].not_allowed.size() >= SQRTN - 1) {
            cout << apply_naive(i) << endl;
        } else {
            cout << apply_short(i) << endl;
        }
    }

    return 0;
}

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