Submission #750656

#	Time	Username	Problem	Language	Result	Execution time	Memory
750656		Shreyan_Paliwal	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1289 ms	419372 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; // party node
    for (auto i : parties[party].not_allowed) dpvis[i] = true; // set which people can't come

    for (int i = 0; i <= nd; i++) { // do dp from top node to party node, later nodes will never be able to come
        dp[i] = (dpvis[i] ? -1 : 0); // base case, if person can come
        for (auto j : rev[i])
            dp[i] = max(dp[i], dp[j] + (dp[j] != -1)); // for each edge into, update dp[i]
    }

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

void unite(int a, int b, vector<pair<int,int>>& fin) { // merges two tracks of SQRTN values
    int ac = 0, bc = 0; // counters for a [new node], b [from node]
    while (fin.size() < SQRTN && (ac < track[a].size() || bc < track[b].size())) { // fin hasn't reached max capacity and at least one group still has smth to give
        if (bc == track[b].size() || (ac < track[a].size() && track[a][ac].first > track[b][bc].first)) // either second track reached end, or first track exists and is better
            vis[track[a][ac].second] = 1, // set visited to true so no repeats
            fin.push_back(track[a][ac++]); // add track to finished
        else 
            vis[track[b][bc].second] = 1, // set visited to true
            fin.push_back(track[b][bc++]), // add track to finished
            fin.back().first++; // also add 1 to val cause edge going into party node

        while (ac < track[a].size() && vis[track[a][ac].second]) ac++; // skip any values that are visited
        while (bc < track[b].size() && vis[track[b][bc].second]) bc++; // skip for other track
    }
    for (auto i : fin) vis[i.second] = 0; // reset vis in SQRTN time
}

void init_short() {
    for (int i = 0; i < n; i++) { // topological order of DAG
        track[i].push_back({0, i}); // add base case 0 to track
        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; // set party node
    for (auto i : parties[party].not_allowed) dpvis[i] = true; // set which people can't visit

    int ans = -1; // answer initially -1
    for (auto i : track[nd]) // for each value in top SQRT N
        if (!dpvis[i.second]) { // if person can visit
            ans = i.first; // set answer, not gonna get better so break
            break;
        }

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

    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) {
            cout << apply_naive(i) << endl; // apply NAIVE for the <= SQRTN times that O(N) not_allowed happens
        } else {
            cout << apply_short(i) << endl; // apply SHORT for the O(N) times that O(SQRT N) can appear.
        }
    }

    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void unite(int, int, std::vector<std::pair<int, int> >&)':
bitaro.cpp:38:38: 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 && (ac < track[a].size() || bc < track[b].size())) { // fin hasn't reached max capacity and at least one group still has smth to give
      |                                   ~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:38:62: 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 && (ac < track[a].size() || bc < track[b].size())) { // fin hasn't reached max capacity and at least one group still has smth to give
      |                                                           ~~~^~~~~~~~~~~~~~~~~
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)) // either second track reached end, or first track exists and is better
      |             ~~~^~~~~~~~~~~~~~~~~~
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)) // either second track reached end, or first track exists and is better
      |                                       ~~~^~~~~~~~~~~~~~~~~
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++; // skip any values that are visited
      |                ~~~^~~~~~~~~~~~~~~~~
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++; // skip for other track
      |                ~~~^~~~~~~~~~~~~~~~~

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