Submission #852933

#	Time	Username	Problem	Language	Result	Execution time	Memory
852933		gun_gan	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1793 ms	328580 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MX = 1e5 + 5, B = 250;
 
int N, M, Q;
 
vector<int> g[MX];
int dist[MX], deg[MX];
bool vis[MX];
bool done[MX];
 
vector<pair<int,int>> vec[MX];
 
void merge(int u, int v) { // merge u to v
      for(auto &[x, y] : vec[u]) x++;
 
      vector<pair<int,int>> res;
 
      int i = 0, j = 0;
      for(; i < vec[u].size() && j < vec[v].size(); ) {
            if(vec[u][i] > vec[v][j]) {
                  if(!done[vec[u][i].second]) {
                        done[vec[u][i].second] = 1;
                        res.push_back(vec[u][i]);
                  }
                  i++;
            } else {
                  if(!done[vec[v][j].second]) {
                        done[vec[v][j].second] = 1;
                        res.push_back(vec[v][j]);
                  }
                  j++;
            }
      }
 
      while(i < vec[u].size()) {
            if(!done[vec[u][i].second]) {
                  done[vec[u][i].second] = 1;
                  res.push_back(vec[u][i]);
            }
            i++;
      }
 
      while(j < vec[v].size()) {
            if(!done[vec[v][j].second]) {
                  done[vec[v][j].second] = 1;
                  res.push_back(vec[v][j]);
            }
            j++;
      }
 
      while(res.size() > B) {
            done[res.back().second] = 0;
            res.pop_back();
      }
      for(auto [x, y] : res) done[y] = 0;

      swap(res, vec[v]);
 
      for(auto &[x, y] : vec[u]) x--;
}
 
int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);
 
      cin >> N >> M >> Q;
 
      for(int i = 0; i < M; i++) {
            int u, v;
            cin >> u >> v;
 
            g[u].push_back(v);
            deg[v]++;
      }
 
      queue<int> q;
 
      for(int i = 1; i <= N; i++) {
            if(!deg[i]) q.push(i);
            vec[i].push_back({0, i});
      }
 
      while(!q.empty()) {
            auto v = q.front(); q.pop();
 
            for(auto u : g[v]) {
                  merge(v, u);
                  deg[u]--;
                  if(!deg[u]) 
                        q.push(u);
            }
      }
 
      for(int j = 0; j < Q; j++) {
            int tj, yj;
            cin >> tj >> yj;
 
            if(yj + 1 < B) {
                  int res = -1;
                  vector<int> v;
 
                  for(int i = 0; i < yj; i++) {
                        int x;
                        cin >> x;
 
                        v.push_back(x);
                        vis[x] = 1;
                  }
 
                  for(auto [y, x] : vec[tj]) {
                        // cout << y << " " << x << '\n';
                        if(!vis[x]) res = max(res, y);
                  }
 
                  cout << res << '\n';
 
                  for(auto x : v) vis[x] = 0;
            } else {
 
                  for(int i = 1; i <= N; i++) {
                        deg[i] = 0;
                        dist[i] = -1;
                        vis[i] = 0;
                  }
 
                  for(int i = 0; i < yj; i++) {
                        int x;
                        cin >> x;
                        vis[x] = 1;
                  }
 
                  for(int i = 1; i <= N; i++) {
                        for(auto k : g[i]) deg[k]++;
                  }
 
                  queue<int> q;
                  for(int i = 1; i <= N; i++) {
                        if(!deg[i]) 
                              q.push(i);

                        if(!vis[i]) dist[i] = 0; 
                  }
 
                  while(!q.empty()) {
                        auto v = q.front(); q.pop();
                        for(auto u : g[v]) {
                              deg[u]--;
                              if(dist[v] >= 0)
                                    dist[u] = max(dist[u], dist[v] + 1);

                              if(!deg[u]) 
                                    q.push(u);
                        }
                  }
 
                  cout << dist[tj] << '\n';

                  for(int i = 1; i <= N; i++) {
                        deg[i] = 0;
                        dist[i] = -1;
                        vis[i] = 0;
                  }
            }
            
      }
 
 
}

Compilation message (stderr)

bitaro.cpp: In function 'void merge(int, int)':
bitaro.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |       for(; i < vec[u].size() && j < vec[v].size(); ) {
      |             ~~^~~~~~~~~~~~~~~
bitaro.cpp:22:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |       for(; i < vec[u].size() && j < vec[v].size(); ) {
      |                                  ~~^~~~~~~~~~~~~~~
bitaro.cpp:38:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |       while(i < vec[u].size()) {
      |             ~~^~~~~~~~~~~~~~~
bitaro.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |       while(j < vec[v].size()) {
      |             ~~^~~~~~~~~~~~~~~

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