Submission #112467

#	Time	Username	Problem	Language	Result	Execution time	Memory
112467		choikiwon	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1485 ms	221692 KiB

bitaro

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

typedef pair<int, int> pii;

const int MN = 100010;
const int SQ = 300;

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

vector<pii> mrg(vector<pii> &a, vector<pii> &b) {
    vector<pii> ret;

    int pos1 = 0, pos2 = 0;
    while(ret.size() < SQ && pos1 < a.size() && pos2 < b.size()) {
        if(used[ a[pos1].second ]) pos1++;
        if(used[ b[pos2].second ]) pos2++;

        if(a[pos1].first > b[pos2].first + 1) ret.push_back(a[pos1]), used[ a[pos1].second ] = 1, pos1++;
        else ret.push_back(pii(b[pos2].first + 1, b[pos2].second)), used[ b[pos2].second ] = 1, pos2++;
    }
    while(ret.size() < SQ && pos1 < a.size()) {
        if(used[ a[pos1].second ]) pos1++;
        ret.push_back(a[pos1]), used[ a[pos1].second ] = 1, pos1++;
    }
    while(ret.size() < SQ && pos2 < b.size()) {
        if(used[ b[pos2].second ]) pos2++;
        ret.push_back(pii(b[pos2].first + 1, b[pos2].second)), used[ b[pos2].second ] = 1, pos2++;
    }

    for(int i = 0; i < ret.size(); i++) used[ ret[i].second ] = 0;
    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 < radj[u].size(); i++) {
        int v = radj[u][i];
        vector<pii> tmp = dp1(v);
        ret = mrg(ret, tmp);
    }

    return ret;
}

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

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

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

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

        adj[u].push_back(v);
        radj[v].push_back(u);
    }

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

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

        if(y > SQ) {
            memset(cc2, -1, sizeof(cc2));
            X = t;

            int ans = -1;
            for(int j = 0; j < N; j++) if(!chk[j]) ans = max(ans, dp2(j));
            printf("%d\n", ans);
        }
        else {
            vector<pii> tmp = dp1(t);

            int ans = -1;
            for(int j = 0; j < tmp.size(); j++) if(!chk[ tmp[j].second ]) {
                ans = tmp[j].first;
                break;
            }

            printf("%d\n", ans);
        }

        for(int j = 0; j < y; j++) chk[ c[j] ] = 0;
    }
}

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:17:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ret.size() < SQ && pos1 < a.size() && pos2 < b.size()) {
                              ~~~~~^~~~~~~~~~
bitaro.cpp:17:54: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ret.size() < SQ && pos1 < a.size() && pos2 < b.size()) {
                                                 ~~~~~^~~~~~~~~~
bitaro.cpp:24:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ret.size() < SQ && pos1 < a.size()) {
                              ~~~~~^~~~~~~~~~
bitaro.cpp:28:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ret.size() < SQ && pos2 < b.size()) {
                              ~~~~~^~~~~~~~~~
bitaro.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ret.size(); i++) used[ ret[i].second ] = 0;
                    ~~^~~~~~~~~~~~
bitaro.cpp: In function 'std::vector<std::pair<int, int> > dp1(int)':
bitaro.cpp:44:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < radj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int dp2(int)':
bitaro.cpp:61: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:101:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < tmp.size(); j++) if(!chk[ tmp[j].second ]) {
                            ~~^~~~~~~~~~~~
bitaro.cpp:69: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:72:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf("%d %d", &u, &v);
                   ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:80: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:85:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &c[j]);
             ~~~~~^~~~~~~~~~~~~

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