Submission #750648

#	Time	Username	Problem	Language	Result	Execution time	Memory
750648		Shreyan_Paliwal	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	1746 ms	524288 KiB

bitaro

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

const int maxn = 100005;
const int SQRTN = 330;

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

int n, m, q;
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 a, int b, vector<pair<int,int>>& fin) {
    int ac = 0, bc = 0;
    while (fin.size() < SQRTN < 5 && (ac < track[a].size() || bc < track[b].size())) {
        if (bc == track[b].size() || (ac < track[a].size() && track[a][ac].first > track[b][bc].first))
            vis[track[a][ac].second] = 1, 
            fin.push_back(track[a][ac++]);
        else 
            vis[track[b][bc].second] = 1,
            fin.push_back(track[b][bc++]),
            fin.back().first++;

        while (ac < track[a].size() && vis[track[a][ac].second]) ac++;
        while (bc < track[b].size() && vis[track[b][bc].second]) bc++;
    }
    for (auto i : fin) vis[i.second] = 0;
}

void init_short() {
    for (int i = 0; i < n; i++) {
        track[i].push_back({0, i});
        for (auto j : rev[i]) {
            // merge [j+1] into [i]
            vector<pair<int,int>> fin; // place holder for merged array
            unite(i, j, fin); // merges j into i while adding 1 to j, stores in fin
            swap(track[i], fin); // i is now fin, let legacy i be deconstructed through 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--;
        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;
}

Compilation message (stderr)

bitaro.cpp: In function 'void unite(int, int, std::vector<std::pair<int, int> >&)':
bitaro.cpp:38:31: warning: comparison of constant '5' with boolean expression is always true [-Wbool-compare]
   38 |     while (fin.size() < SQRTN < 5 && (ac < track[a].size() || bc < track[b].size())) {
      |            ~~~~~~~~~~~~~~~~~~~^~~
bitaro.cpp:38:23: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
   38 |     while (fin.size() < SQRTN < 5 && (ac < track[a].size() || bc < track[b].size())) {
      |            ~~~~~~~~~~~^~~~~~~
bitaro.cpp:38:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     while (fin.size() < SQRTN < 5 && (ac < track[a].size() || bc < track[b].size())) {
      |                                       ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:38:66: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     while (fin.size() < SQRTN < 5 && (ac < track[a].size() || bc < track[b].size())) {
      |                                                               ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         if (bc == track[b].size() || (ac < track[a].size() && track[a][ac].first > track[b][bc].first))
      |             ~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:39:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         if (bc == track[b].size() || (ac < track[a].size() && track[a][ac].first > track[b][bc].first))
      |                                       ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         while (ac < track[a].size() && vis[track[a][ac].second]) ac++;
      |                ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         while (bc < track[b].size() && vis[track[b][bc].second]) bc++;
      |                ~~~^~~~~~~~~~~~~~~~~

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