oj.uz

Submission #112471

# Submission time Handle Problem Language Result Execution time Memory
112471 2019-05-20T06:26:25 Z choikiwon Bitaro’s Party (JOI18_bitaro) C++17
0 / 100
 10 ms 7936 KB 
#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];
            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 < N; 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

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:30:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ret.size() < SQ && pos1 < a.size()) {
                              ~~~~~^~~~~~~~~~
bitaro.cpp:37:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ret.size() < SQ && pos2 < b.size()) {
                              ~~~~~^~~~~~~~~~
bitaro.cpp:45: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:56: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:67: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:105: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:75: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:78: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:87: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:92:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &c[j]);
             ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7296 KB Output is correct
2 Correct 7 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 7 ms 7424 KB Output is correct
5 Incorrect 10 ms 7936 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7296 KB Output is correct
2 Correct 7 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 7 ms 7424 KB Output is correct
5 Incorrect 10 ms 7936 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7296 KB Output is correct
2 Correct 7 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 7 ms 7424 KB Output is correct
5 Incorrect 10 ms 7936 KB Output isn't correct
6 Halted 0 ms 0 KB -