Submission #637079

#	Time	Username	Problem	Language	Result	Execution time	Memory
637079		Ronin13	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1731 ms	423564 KiB

bitaro

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int NMAX = 100001;
vector <vector <int> > g(NMAX);

int bl = 500;

int main(){
    int n; cin >> n;
    int m; cin >> m;
    int q; cin >> q;
    for(int i= 1; i <= m; i++){
        int u, v; cin >> u >> v;
        g[v].pb(u);
    }
    vector <int> ans(q + 1, -1);
    vector <vector <int> > x(q + 1);
    vector <int> d(n + 1, -1);
    vector <vector <int> > qq(n + 1);
    vector <bool> used(n + 1, false);
    for(int i = 1; i <= q; i++){
        int t, y; cin >> t >> y;

        for(int j = 1; j <= y; j++){
            int v; cin >> v;
            x[i].pb(v);
            used[v] = true;
        }
        if(y >= bl){
            d[t] = 0;
            for(int j = t; j >= 1; j--){
                if(!used[j])ans[i] = max(ans[i], d[j]);
                if(d[j] == -1) continue;
                for(int to : g[j])
                    d[to] = max(d[to], d[j] + 1);
            }
            for(int j = 1; j <= n; j++) d[j] = -1;

        }
        else qq[t].pb(i);
        for(int j : x[i]) used[j] = false;
    }
    vector <vector <pii> > res(n + 1);
    vector <int> ind(n + 1);

    for(int i = 1; i <= n; i++){
        while(res[i].size() < bl){
            pii mx = {-1, 0};
            int  mxi;
            for(int to : g[i]){
                int x = ind[to];
                if(ind[to] == res[to].size()) continue;
                while(x < res[to].size() && used[res[to][x].s])
                    ind[to]++, x= ind[to];
                if(x == res[to].size()) continue;
                if(mx < res[to][ind[to]]){
                    mx = res[to][ind[to]];
                    mxi = to;
                }
            }
            if(mx.f == -1) break;
            mx.f++;
            res[i].pb(mx);
            used[res[mxi][ind[mxi]].s] = true;
            ind[mxi]++;
        }
        for(int to : g[i]){
            for(auto x : res[to])used[x.s] = false;
            ind[to] = 0;
        }
        if(res[i].size() < bl) res[i].pb({0, i});
    }
   // cout << 1;
    for(int i = 1; i <= n; i++){

        for(int v : qq[i]){
            int ind = 0;
            for(int to : x[v]){
                used[to] = true;
            }
            for(int j = 0; j < res[i].size(); j++) {
                if(!used[res[i][j].s]) {
                    ans[v] = res[i][j].f;
                    break;
                }
            }
            for(int to : x[v]) used[to] = false;
        }
    }
    for(int i= 1; i <= q; i++) cout << ans[i] << "\n";
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:55:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |         while(res[i].size() < bl){
      |               ~~~~~~~~~~~~~~^~~~
bitaro.cpp:60:28: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |                 if(ind[to] == res[to].size()) continue;
bitaro.cpp:61:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                 while(x < res[to].size() && used[res[to][x].s])
      |                       ~~^~~~~~~~~~~~~~~~
bitaro.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                 if(x == res[to].size()) continue;
      |                    ~~^~~~~~~~~~~~~~~~~
bitaro.cpp:79:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |         if(res[i].size() < bl) res[i].pb({0, i});
      |            ~~~~~~~~~~~~~~^~~~
bitaro.cpp:89:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             for(int j = 0; j < res[i].size(); j++) {
      |                            ~~^~~~~~~~~~~~~~~
bitaro.cpp:85:17: warning: unused variable 'ind' [-Wunused-variable]
   85 |             int ind = 0;
      |                 ^~~
bitaro.cpp:72:34: warning: 'mxi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |             used[res[mxi][ind[mxi]].s] = true;
      |                                  ^

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