Submission #112482

#	Time	Username	Problem	Language	Result	Execution time	Memory
112482		choikiwon	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1312 ms	220540 KiB

bitaro

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

typedef pair<int, int> pii;

const int MN = 100010;
const int SQ = 200;

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++;
            continue;
        }
        if(used[ b[pos2].second ]) {
            pos2++;
            continue;
        }

        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++;
            continue;
        }
        ret.push_back(a[pos1]);
        used[ a[pos1].second ] = 1;
        pos1++;
    }
    while(ret.size() < SQ && pos2 < b.size()) {
        if(used[ b[pos2].second ]) {
            pos2++;
            continue;
        }
        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> dp1[MN];
int dp2[MN];

void solve1() {
    for(int u = 0; u < N; u++) {
        dp1[u].push_back({0, u});

        for(int i = 0; i < radj[u].size(); i++) {
            int v = radj[u][i];
            dp1[u] = mrg(dp1[u], dp1[v]);
        }
    }
}

void solve2(int x) {
    dp2[x] = 0;
    for(int u = x - 1; u >= 0; u--) {
        dp2[u] = -1e9;
        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            if(v > x) continue;
            dp2[u] = max(dp2[u], dp2[v] + 1);
        }
    }
}

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);
    }

    solve1();
    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) {
            solve2(t);

            int ans = -1;
            for(int j = 0; j <= t; j++) if(!chk[j]) ans = max(ans, dp2[j]);
            printf("%d\n", ans);
        }
        else {
            int ans = -1;
            for(int j = 0; j < dp1[t].size(); j++) if(!chk[ dp1[t][j].second ]) {
                ans = dp1[t][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:38:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ret.size() < SQ && pos1 < a.size()) {
                              ~~~~~^~~~~~~~~~
bitaro.cpp:47:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ret.size() < SQ && pos2 < b.size()) {
                              ~~~~~^~~~~~~~~~
bitaro.cpp:57: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 'void solve1()':
bitaro.cpp:68:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < radj[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~~
bitaro.cpp: In function 'void solve2(int)':
bitaro.cpp:79:26: 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:118:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < dp1[t].size(); j++) if(!chk[ dp1[t][j].second ]) {
                            ~~^~~~~~~~~~~~~~~
bitaro.cpp:88: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:91: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:100: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:105: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: 86 / 86