Submission #201436

#	Time	Username	Problem	Language	Result	Execution time	Memory
201436		theStaticMind	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	18 ms	9592 KiB

bitaro

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

vector<int> adj[100005];
unordered_map<int, int> 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][x] = 0;
            vector<ii> temp; 
            for(unordered_map<int, int>::iterator itr = data[x].begin(); itr != data[x].end() ; itr++) temp.pb({itr->second, itr->first});

            sort(all(temp), greater<ii>());

            for(int i = 0; i < adj[x].size(); i++){
                  int y = adj[x][i];
                  for(int j = 0; j < temp.size() && j < sq; j++){
                        data[y][temp[j].second] = max(data[y][temp[j].second], temp[j].first + 1);
                  }
                  
            }

      }

      while(q--){

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

            int ans = -1;
            for(unordered_map<int, int>::iterator itr = data[X].begin(); itr != data[X].end(); itr++){
                  if(ban.count(itr->first))continue;
                  ans = max(ans, itr->second);
            }
            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:35:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < adj[x].size(); i++){
                            ~~^~~~~~~~~~~~~~~
bitaro.cpp:37:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int j = 0; j < temp.size() && j < sq; j++){
                                  ~~^~~~~~~~~~~~~
bitaro.cpp:65:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for(int i = 0; i < adj[x].size(); i++){
                                        ~~^~~~~~~~~~~~~~~

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