Submission #50146

#	Time	Username	Problem	Language	Result	Execution time	Memory
50146		spencercompton	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	2092 ms	426024 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
int buf;
bool inside[100000];
vector<pair<int, int> > mg(vector<pair<int, int> > a, vector<pair<int, int> > b){
    //first = val
    //second = loc
    vector<pair<int, int> > ret;
    int p1 = 0;
    int p2 = 0;
    int sz1 = a.size();
    int sz2 = b.size();
    while((p1<sz1 || p2<sz2) && ret.size()<buf){
        bool add1 = false;
        if(p1==sz1){
            //add2
        }
        else if(p2==sz2){
            add1 = true;
        }
        else{
            if(a[p1]<b[p2]){
                add1 = true;
            }
            else{
                //add2
            }
        }
        if(add1){
            if(inside[a[p1].second]){
                p1++;
                continue;
            }
            inside[a[p1].second] = true;
            ret.push_back(a[p1++]);
        }
        else{
            if(inside[b[p2].second]){
                p2++;
                continue;
            }
            inside[b[p2].second] = true;
            ret.push_back(b[p2++]);
        }
    }
    for(int i = 0; i<ret.size(); i++){
        inside[ret[i].second] = false;
    }
    return ret;
}
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m, q;
    cin >> n >> m >> q;
    int answers[q];
    for(int i = 0; i<q; i++){
        answers[i]=-42;
    }
    for(int i = 0; i<n; i++){
        inside[i] = false;
    }
    buf = 333;
    // buf = 0;
    // buf = 1000000;
    vector<pair<vector<int>, int> > queries[n];
    vector<int> to[n];
    vector<int> from[n];
    for(int i = 0; i<m; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        assert(a<b);
        to[a].push_back(b);
        from[b].push_back(a);
    }
    for(int i = 0; i<q; i++){
        int t, len;
        cin >> t >> len;
        t--;
        vector<int> x;
        for(int j = 0; j<len; j++){
            int v;
            cin >> v;
            v--;
            x.push_back(v);
        }
        queries[t].push_back(make_pair(x,i));
    }
    vector<pair<int, int> > best[n];
    for(int i = 0; i<n; i++){
        best[i].push_back(make_pair(0,i));
    }
    for(int i = 0; i<n; i++){
        vector<pair<int, int> > li;
        //first is distance second is loc
        for(int z = 0; z<queries[i].size(); z++){
            vector<int> v = queries[i][z].first;
            if(v.size()>=buf){
                if(li.size()==0){
                    int score[i+1];
                    for(int j = 0; j<=i; j++){
                        score[j] = -1;
                    }
                    vector<int> all[i+1];
                    score[i] = 0;
                    for(int j = i; j>=0; j--){
                        int now = j;
                        if(score[now]==-1){
                            continue;
                        }
                        all[score[now]].push_back(now);
                        for(int k = 0; k<from[now].size(); k++){
                            int val = from[now][k];
                            score[val] = max(score[val],score[now]+1);
                        }
                    }
                    for(int j = 0; j<=i; j++){
                        for(int k = 0; k<all[j].size(); k++){
                            li.push_back(make_pair(j,all[j][k]));
                        }
                    }
                }
                for(int j = 0; j<v.size(); j++){
                    inside[v[j]] = true;
                }
                int ret = -1;
                for(int j = li.size()-1; j>=0; j--){
                    if(!inside[li[j].second]){
                        ret = li[j].first;
                        break;
                    }
                }
                for(int j = 0; j<v.size(); j++){
                    inside[v[j]] = false;
                }
                answers[queries[i][z].second] = ret;
            }
            else{
                for(int j = 0; j<v.size(); j++){
                    inside[v[j]] = true;
                }
                int ret = -1;
                for(int j = 0; j<best[i].size(); j++){
                    if(!inside[best[i][j].second]){
                        ret = -best[i][j].first;
                        break;
                    }
                }
                for(int j = 0; j<v.size(); j++){
                    inside[v[j]] = false;
                }
                answers[queries[i][z].second] = ret;
            }
        }
        
        for(int j = 0; j<best[i].size(); j++){
            best[i][j].first--;
        }
        for(int j = 0; j<to[i].size(); j++){
            int loc = to[i][j];
            best[loc] = mg(best[loc],best[i]);
        }
        best[i].clear();
    }
    for(int i = 0; i<q; i++){
        assert(answers[i]>=-1);
        cout << answers[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > mg(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:13:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while((p1<sz1 || p2<sz2) && ret.size()<buf){
                                 ~~~~~~~~~~^~~~
bitaro.cpp:46:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i<ret.size(); i++){
                    ~^~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:99:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int z = 0; z<queries[i].size(); z++){
                        ~^~~~~~~~~~~~~~~~~~
bitaro.cpp:101:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(v.size()>=buf){
                ~~~~~~~~^~~~~
bitaro.cpp:115:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for(int k = 0; k<from[now].size(); k++){
                                        ~^~~~~~~~~~~~~~~~~
bitaro.cpp:121:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for(int k = 0; k<all[j].size(); k++){
                                        ~^~~~~~~~~~~~~~
bitaro.cpp:126:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j = 0; j<v.size(); j++){
                                ~^~~~~~~~~
bitaro.cpp:136:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j = 0; j<v.size(); j++){
                                ~^~~~~~~~~
bitaro.cpp:142:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j = 0; j<v.size(); j++){
                                ~^~~~~~~~~
bitaro.cpp:146:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j = 0; j<best[i].size(); j++){
                                ~^~~~~~~~~~~~~~~
bitaro.cpp:152:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j = 0; j<v.size(); j++){
                                ~^~~~~~~~~
bitaro.cpp:159:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j<best[i].size(); j++){
                        ~^~~~~~~~~~~~~~~
bitaro.cpp:162:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j<to[i].size(); j++){
                        ~^~~~~~~~~~~~~

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