Submission #201452

#	Time	Username	Problem	Language	Result	Execution time	Memory
201452		theStaticMind	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1824 ms	116832 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<int> radj[100005];
vector<ii> data[100005];
vector<bool> vis(100005, false);


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

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

            for(int i = 0; i < radj[x].size(); i++){
                  int y = radj[x][i];
                  for(int j = 0; j < data[y].size(); j++){
                        data[x].pb({data[y][j].first + 1, data[y][j].second});
                  }
                  
            }

            data[x].pb({0, x});
            sort(all(data[x]), greater<ii>());
            vector<ii>temp;
            int w = 0;
            for(int i = 0; i < data[x].size() && w < sq; i++){
                  if(vis[data[x][i].second])continue;
                  temp.pb(data[x][i]);
                  vis[data[x][i].second] = true;
                  w++;
            }
            swap(temp, data[x]);
            temp.clear();
            for(int i = 0; i < data[x].size(); i++)vis[data[x][i].second] = false;

      }

      while(q--){

            int X, k;
            cin >> X >> k;
            vector<int> ban;
            for(int i = 0; i < k; i++){
                  int x;
                  cin >> x;
                  ban.pb(x);
                  vis[x] = true;
            }

            int ans = -1;
            for(int i = 0; i < data[X].size(); i++){
                  if(vis[data[X][i].second])continue;
                  ans = max(ans, data[X][i].first);
            }
            if(ans == -1){
                  vector<int> val(100005, -1e9);
                  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(vis[x]) continue;
                        ans = max(ans , val[x]);
                  }
            }
            for(int i = 0; i < k; i++) vis[ban[i]] = false;
            cout << ans << "\n";
      }
}

Compilation message (stderr)

bitaro.cpp: In function 'int32_t main()':
bitaro.cpp:32:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < radj[x].size(); i++){
                            ~~^~~~~~~~~~~~~~~~
bitaro.cpp:34:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int j = 0; j < data[y].size(); j++){
                                  ~~^~~~~~~~~~~~~~~~
bitaro.cpp:44:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < data[x].size() && w < sq; i++){
                            ~~^~~~~~~~~~~~~~~~
bitaro.cpp:52:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < data[x].size(); i++)vis[data[x][i].second] = false;
                            ~~^~~~~~~~~~~~~~~~
bitaro.cpp:69:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < data[X].size(); i++){
                            ~~^~~~~~~~~~~~~~~~
bitaro.cpp:77: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: 7 / 7
• Subtask 3: 86 / 86