Submission #201447

#	Time	Username	Problem	Language	Result	Execution time	Memory
201447		theStaticMind	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2127 ms	485496 KiB

bitaro

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

vector<int> adj[100005];
vector<ii> data[100005];


int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      int n, m, q;
      cin >> n >> m >> q;
      int sq = sqrt(n);

      for(int i = 0; i < m; i++){
            int x, y;
            cin >> x >> y;
            adj[min(x, y)].pb(max(x, y));
      }
      for(int x = 1; x <= n; x++){

            data[x].pb({0, x});
            sort(all(data[x]), greater<ii>());
            vector<ii>temp;
            unordered_set<int> vis;
            int w = 0;
            for(int i = 0; i < data[x].size() && w < sq; i++){
                  if(vis.count(data[x][i].second))continue;
                  temp.pb(data[x][i]);
                  vis.insert(data[x][i].second);
                  w++;
            }
            swap(temp, data[x]);
            temp.clear();
            for(int i = 0; i < adj[x].size(); i++){
                  int y = adj[x][i];
                  for(int j = 0; j < data[x].size(); j++){
                        data[y].pb({data[x][j].first + 1, data[x][j].second});
                  }
                  
            }

      }

      while(q--){

            int X, k;
            cin >> X >> k;
            unordered_set<int> ban;
            for(int i = 0; i < k; i++){
                  int x;
                  cin >> x;
                  if(x <= X)
                  ban.insert(x);
            }

            int ans = -1;
            for(int i = 0; i < data[X].size(); i++){
                  if(ban.count(data[X][i].second))continue;
                  ans = max(ans, data[X][i].first);
            }
            if(ans == -1){
                  vector<int> val(100005, -INF);
                  val[X] = 0;
                  for(int x = X; x >= 1; x--){
                        for(int i = 0; i < adj[x].size(); i++){
                              int y = adj[x][i];
                              val[x] = max(val[x], val[y] + 1);
                        }
                        if(ban.count(x)) continue;
                        ans = max(ans , val[x]);
                  }
            }
            cout << ans << "\n";
      }
}

Compilation message (stderr)

bitaro.cpp: In function 'int32_t main()':
bitaro.cpp:34:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < data[x].size() && w < sq; i++){
                            ~~^~~~~~~~~~~~~~~~
bitaro.cpp:42:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < adj[x].size(); i++){
                            ~~^~~~~~~~~~~~~~~
bitaro.cpp:44:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int j = 0; j < data[x].size(); j++){
                                  ~~^~~~~~~~~~~~~~~~
bitaro.cpp:65:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < data[X].size(); i++){
                            ~~^~~~~~~~~~~~~~~~
bitaro.cpp:73:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for(int i = 0; i < adj[x].size(); i++){
                                        ~~^~~~~~~~~~~~~~~

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