Submission #936261

#	Time	Username	Problem	Language	Result	Execution time	Memory
936261		velislavgarkov	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1202 ms	371540 KiB

bitaro

#include <iostream>
#include <vector>
using namespace std;
#define endl '\n'
const int MAXN=1e5+10;
const int BUCK=450;
vector <int> v[MAXN], op[MAXN];
vector <pair <int,int> > best[MAXN], help;
int lazy[MAXN], dp[MAXN];
bool used[MAXN];
int n;
void merge_sort(int i, int j) {
    int bri, brj, cnt, gr;
    bri=brj=cnt=0;
    while (cnt<BUCK && (bri<best[i].size() || brj<best[j].size())) {
        if (bri==best[i].size()) {
            help.push_back(best[j][brj]);
            used[best[j][brj].second]=true;
            brj++;
        } else if (brj==best[j].size()) {
            help.push_back(best[i][bri]);
            used[best[i][bri].second]=true;
            bri++;
        } else if (used[best[i][bri].second]) {
            bri++;
            continue;
        } else if (used[best[j][brj].second]) {
            brj++;
            continue;
        } else if (best[i][bri].first>best[j][brj].first) {
            help.push_back(best[i][bri]);
            used[best[i][bri].second]=true;
            bri++;
        } else {
            help.push_back(best[j][brj]);
            used[best[j][brj].second]=true;
            brj++;
        }
        cnt++;
    }
    best[i].clear();
    gr=help.size();
    best[i].resize(gr);
    for (int k=0;k<gr;k++) {
        best[i][k]=help[k];
        used[help[k].second]=false;
    }
    help.clear();
}
int find_dp(int x) {
    for (int i=1;i<=x;i++) {
        dp[i]=0;
        if (used[i]) dp[i]=-1;
        for (auto j:op[i]) {
            if (dp[j]==-1) continue;
            dp[i]=max(dp[i],dp[j]+1);
        }
    }
    return dp[x];
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, q, a, b;
    cin >> n >> m >> q;
    for (int i=1;i<=m;i++) {
        cin >> a >> b;
        v[a].push_back(b);
        op[b].push_back(a);
    }
    for (int i=1;i<=n;i++) {
        best[i].push_back({-1,i});
        for (auto j:op[i]) merge_sort(i,j);
        //cout << i << ':' << endl;
        for (int j=0;j<best[i].size();j++) {
            best[i][j].first++;
            //cout << best[i][j].first << ' ' << best[i][j].second << endl;
        }
    }
    int t, br;
    for (int i=0;i<q;i++) {
        cin >> t >> br;
        for (int j=0;j<br;j++) cin >> lazy[j];
        for (int j=0;j<br;j++) used[lazy[j]]=true;
        if (br<BUCK) {
            int ans=-1;
            for (auto j:best[t]) {
                if (used[j.second]) continue;
                ans=j.first;
                break;
            }           
            cout << ans << endl;
        } else cout << find_dp(t) << endl;
        for (int j=0;j<br;j++) used[lazy[j]]=false;
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void merge_sort(int, int)':
bitaro.cpp:15:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     while (cnt<BUCK && (bri<best[i].size() || brj<best[j].size())) {
      |                         ~~~^~~~~~~~~~~~~~~
bitaro.cpp:15:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     while (cnt<BUCK && (bri<best[i].size() || brj<best[j].size())) {
      |                                               ~~~^~~~~~~~~~~~~~~
bitaro.cpp:16: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]
   16 |         if (bri==best[i].size()) {
      |             ~~~^~~~~~~~~~~~~~~~
bitaro.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         } else if (brj==best[j].size()) {
      |                    ~~~^~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int j=0;j<best[i].size();j++) {
      |                      ~^~~~~~~~~~~~~~~

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