Submission #706095

#	Time	Username	Problem	Language	Result	Execution time	Memory
706095		lukameladze	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1982 ms	268860 KiB

bitaro

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5, B = 300;
int t,n,m,q,a[N],fix[N],x[N],bad[N],ans[N];
vector <pii> vec[N];
vector <int> v[N],v1[N];
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin>>a>>b;
        v[a].pb(b);
        v1[b].pb(a);
    }
    for (int i = 1; i <= n; i++) {
        vec[i].pb({0, i});
        for (int x : v1[i]) {
            vector < pii > cur; cur = vec[i];
            vector < pii > upd; upd = vec[x];
            vector < pii > cur_n;
            int cur_id = 0, upd_id = 0;
            while ((cur_id < cur.size() || upd_id < upd.size()) && cur_n.size() <= B) {
//                if (upd_id < upd.size()) upd[upd_id].f++;
                if (cur_id == cur.size() || (upd_id != upd.size() && (upd[upd_id].f + 1) >= cur[cur_id].f)) {
                    if (fix[upd[upd_id].s]) {
                        upd_id++; continue;
                    }
                    cur_n.pb({upd[upd_id].f + 1, upd[upd_id].s}); fix[upd[upd_id].s] = 1; upd_id++; continue;
                }
                if (fix[cur[cur_id].s]) {
                    cur_id++; continue;
                }
                cur_n.pb(cur[cur_id]); fix[cur[cur_id].s] = 1; cur_id++;
            }
            vec[i] = cur_n;
//            cout<<i<<" --- > "<<vec[i].size()<<"\n";
            for (pii sth : cur_n) fix[sth.s] = 0;
        }
    }
    while(q--) {
        int vert, y;
        cin>>vert>>y;
        for (int i = 1; i <= y; i++) {
            cin>>x[i];
            bad[x[i]] = 1;
        }
        if (y < B) {
            int ff = 0;
            for (pii sth : vec[vert]) {
                if (!bad[sth.s]) {
                    cout<<sth.f<<"\n"; ff = 1;break;
                }
            } 
            if (!ff) cout<<-1<<"\n";
        } else {
            for (int i = 1; i <= n; i++) {
                if (bad[i]) ans[i] = -1e9;
                else ans[i] = 0;
            }
            for (int i = 1; i <= n; i++) {
                for (int to : v[i]) {
                    ans[to] = max(ans[to], ans[i] + 1);
                }
            }
            cout<<(ans[vert] < 0 ? -1 : ans[vert])<<"\n";
        }
        
        for (int i = 1; i <= y; i++) {
            bad[x[i]] = 0;
        }
        
    }
}

Compilation message (stderr)

bitaro.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 | main() {
      | ^~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:28:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |             while ((cur_id < cur.size() || upd_id < upd.size()) && cur_n.size() <= B) {
      |                     ~~~~~~~^~~~~~~~~~~~
bitaro.cpp:28:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |             while ((cur_id < cur.size() || upd_id < upd.size()) && cur_n.size() <= B) {
      |                                            ~~~~~~~^~~~~~~~~~~~
bitaro.cpp:30:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |                 if (cur_id == cur.size() || (upd_id != upd.size() && (upd[upd_id].f + 1) >= cur[cur_id].f)) {
      |                     ~~~~~~~^~~~~~~~~~~~~
bitaro.cpp:30:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |                 if (cur_id == cur.size() || (upd_id != upd.size() && (upd[upd_id].f + 1) >= cur[cur_id].f)) {
      |                                              ~~~~~~~^~~~~~~~~~~~~

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