Submission #113860

#	Time	Username	Problem	Language	Result	Execution time	Memory
113860		popovicirobert	Park (JOI17_park)	C++14	0 / 100	60 ms	512 KiB

park

#include "park.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1400;

vector < vector <int> > g;
static int Place[MAXN];
static bool vis[MAXN];

inline void bfs(int nod, vector <int> &ord) {

    queue <int> Q;
    Q.push(nod);
    vis[nod] = 1;

    while(Q.size()) {
        nod = Q.front();
        Q.pop();

        ord.push_back(nod);

        for(auto it : g[nod]) {
            if(vis[it] == 0) {
                vis[it] = 1;
                Q.push(it);
            }
        }
    }
}

static bool block[MAXN];

inline bool check(vector <int> &ord, int pos1, int pos2, int b) {
    Place[b] = 1;
    for(int i = pos1; i <= pos2; i++) {
        if(block[ord[i]] == 0) {
            Place[ord[i]] = 1;
        }
    }

    bool ans;

    if(block[ord[pos1]] || block[b]) {
        ans = 0;
    }
    else {
        ans = Ask(ord[pos1], b, Place);
    }

    /*if(b == 5 && pos1 == 0) {
        cerr << pos1 << " " << pos2 << "\n";
        for(int i = 0; i < ord.size(); i++) {
            cerr << ord[i] << " " << Place[ord[i]] << "\n";
        }
        cerr << ans << "\n\n";
    }*/

    Place[b] = 0;
    for(int i = pos1; i <= pos2; i++) {
        Place[ord[i]] = 0;
    }

    return ans;
}

void Detect(int t, int n) {

    g.resize(n);
    int i;

    vector <int> pos(n);

    for(int nod = 0; nod < n; nod++) {

        for(i = 0; i < nod; i++) {

            if(vis[i] == 1) {
                continue;
            }

            vector <int> ord;
            bfs(i, ord);

            for(i = 0; i < ord.size(); i++) {
                pos[ord[i]] = i;
            }

            /*if(nod == 4) {
                for(auto it : ord) {
                    cerr << it << " ";
                }
                cerr << "\n";
            }*/

            queue <int> Q;
            Q.push(0);

            while(Q.size()) {

                auto cur = Q.front();

                int res = cur - 1;
                for(int step = 1 << 10; step; step >>= 1) {
                    if(res + step <= (int) ord.size() - 1 && check(ord, cur, res + step, nod) == 0) {
                        res += step;
                    }
                }

                res++;

                /*if(nod == 4) {
                    cerr << "\n\n";
                    cerr << ord[cur] << " " << ord[res] << "\n";
                }*/

                if(res == ord.size()) {
                    Q.pop();
                }
                else if(block[ord[res]] == 0) {
                    g[nod].push_back(ord[res]);
                    g[ord[res]].push_back(nod);

                    block[ord[res]] = 1;
                    Q.pop();

                    //cerr << nod << " " << cur << " " << ord[res] << "\n";


                    /*for(auto it : g[ord[res]]) {
                        if(it != nod && pos[it] > pos[ord[res]]) {
                            Q.push(pos[it]);
                        }
                    }*/

                }
                else {
                    Q.pop();
                }

                /*if(nod == 2) {
                    cerr << ord[res] << "\n";
                }*/

            }

            for(auto it : ord) {
                block[it] = 0;
            }
        }

        for(i = 0; i <= nod; i++) {
            vis[i] = 0;
        }

    }


    for(i = 0; i < n; i++) {
        for(auto it : g[i]) {
            if(it > i) {
                Answer(i, it);
            }
        }
    }

}

Compilation message (stderr)

park.cpp: In function 'void Detect(int, int)':
park.cpp:86:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(i = 0; i < ord.size(); i++) {
                        ~~^~~~~~~~~~~~
park.cpp:118:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(res == ord.size()) {
                    ~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30
• Subtask 5: 0 / 23