Submission #45507

#	Time	Username	Problem	Language	Result	Execution time	Memory
45507		choikiwon	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	9 ms	5780 KiB

bitaro

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

typedef pair<int, int> pii;

const int MN = 100010;

int N, M, Q;
vector<int> adj[MN];
map<int, int> chk;

vector<pii> mrg(vector<pii> &a, vector<pii> &b) {
    vector<pii> ret;
    int pos1 = 0, pos2 = 0;
    while(pos1 < a.size() && pos2 < b.size() && ret.size() < sqrt(N)) {
        if(a[pos1].first <= b[pos2].first - 1) ret.push_back(a[pos1++]);
        else ret.push_back({ b[pos2].first - 1, b[pos2].second }), pos2++;
    }
    while(pos1 < a.size() && ret.size() < sqrt(N)) ret.push_back(a[pos1++]);
    while(pos2 < b.size() && ret.size() < sqrt(N)) ret.push_back({ b[pos2].first - 1, b[pos2].second }), pos2++;
    return ret;
}

vector<pii> cc1[MN];
vector<pii> dp1(int u) {
    vector<pii> &ret = cc1[u];
    if(ret.size()) return ret;

    ret.push_back({0, u});
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        vector<pii> tmp = dp1(v);
        ret = mrg(ret, tmp);
    }
    return ret;
}

int cc2[MN];
int dp2(int u) {
    int &ret = cc2[u];
    if(ret != -1) return ret;

    ret = chk[u]? -1e9 : 0;
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        ret = max(ret, 1 + dp2(v));
    }
    return ret;
}

int main() {
    scanf("%d %d %d", &N, &M, &Q);

    for(int i = 0; i < M; i++) {
        int s, e; scanf("%d %d", &s, &e);
        s--; e--;

        adj[e].push_back(s);
    }

    for(int i = 0; i < Q; i++) {
        int t, y; scanf("%d %d", &t, &y);
        t--;

        chk.clear();
        for(int j = 0; j < y; j++) {
            int c; scanf("%d", &c);
            chk[--c] = 1;
        }

        if(y < (int)sqrt(N)) {
            vector<pii> tmp = dp1(t);

            bool ok = false;
            for(int i = 0; i < tmp.size(); i++) if(!chk[ tmp[i].second ]) {
                printf("%d\n", -tmp[i].first);
                ok = true;
                break;
            }
            if(!ok) {
                printf("-1\n");
            }
        }
        else {
            memset(cc2, -1, sizeof(cc2));
            if(dp2(t) > 0) printf("%d\n", dp2(t));
            else printf("-1\n");
        }
    }
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > mrg(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
bitaro.cpp:15:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos1 < a.size() && pos2 < b.size() && ret.size() < sqrt(N)) {
           ~~~~~^~~~~~~~~~
bitaro.cpp:15:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos1 < a.size() && pos2 < b.size() && ret.size() < sqrt(N)) {
                              ~~~~~^~~~~~~~~~
bitaro.cpp:19:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos1 < a.size() && ret.size() < sqrt(N)) ret.push_back(a[pos1++]);
           ~~~~~^~~~~~~~~~
bitaro.cpp:20:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos2 < b.size() && ret.size() < sqrt(N)) ret.push_back({ b[pos2].first - 1, b[pos2].second }), pos2++;
           ~~~~~^~~~~~~~~~
bitaro.cpp: In function 'std::vector<std::pair<int, int> > dp1(int)':
bitaro.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
bitaro.cpp: In function 'int dp2(int)':
bitaro.cpp:44:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:75:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < tmp.size(); i++) if(!chk[ tmp[i].second ]) {
                            ~~^~~~~~~~~~~~
bitaro.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &M, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:55:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int s, e; scanf("%d %d", &s, &e);
                   ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:62:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int t, y; scanf("%d %d", &t, &y);
                   ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:67:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             int c; scanf("%d", &c);
                    ~~~~~^~~~~~~~~~

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