oj.uz

Submission #112459

# Submission time Handle Problem Language Result Execution time Memory
112459 2019-05-20T05:57:42 Z choikiwon Bitaro’s Party (JOI18_bitaro) C++17
0 / 100
 7 ms 5376 KB 
#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];
int chk[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(a[pos1].first > b[pos2].first + 1) ret.push_back(a[pos1++]);
        else ret.push_back(pii(b[pos2].first + 1, b[pos2].second)), pos2++;
    }
    while(ret.size() < SQ && pos1 < a.size()) ret.push_back(a[pos1++]);
    while(ret.size() < SQ && pos2 < b.size()) ret.push_back(pii(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 cc1[u] = 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[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));

            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

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:21:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ret.size() < SQ && pos1 < a.size()) ret.push_back(a[pos1++]);
                              ~~~~~^~~~~~~~~~
bitaro.cpp:22:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ret.size() < SQ && pos2 < b.size()) ret.push_back(pii(b[pos2].first + 1, b[pos2].second)), pos2++;
                              ~~~~~^~~~~~~~~~
bitaro.cpp: In function 'std::vector<std::pair<int, int> > dp1(int)':
bitaro.cpp:33: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:50: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:88: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:58: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:61: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:68: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:73: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 7 ms 5120 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Incorrect 7 ms 5376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Incorrect 7 ms 5376 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Incorrect 7 ms 5376 KB Output isn't correct
6 Halted 0 ms 0 KB -