제출 #852772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
852772		gun_gan	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	654 ms	524288 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 1e5 + 5, B = 330;

int N, M, Q;

vector<int> g[MX];
int dist[MX], deg[MX];
bool vis[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].first > vec[v][j].first) {
                  res.push_back(vec[u][i]);
                  i++;
            } else {
                  res.push_back(vec[v][j]);
                  j++;
            }
      }

      while(i < vec[u].size()) {
            res.push_back(vec[u][i]);
            i++;
      }

      while(j < vec[v].size()) {
            res.push_back(vec[v][j]);
            j++;
      }
 
      while(res.size() > B) res.pop_back();
      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);
      }

      while(!q.empty()) {
            auto v = q.front(); q.pop();

            if(vec[v].size() < B) vec[v].push_back({0, v}); 

            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 < 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();
                        if(!vis[v]) dist[v] = max(dist[v], 0);
                        for(auto u : g[v]) {
                              deg[u]--;
                              if(dist[v] != -1)
                                    dist[u] = max(dist[u], dist[v] + 1);
                              if(!deg[u]) 
                                    q.push(u);
                        }
                  }

                  cout << dist[tj] << '\n';
            }
            
      }


}

컴파일 시 표준 에러 (stderr) 메시지

bitaro.cpp: In function 'void merge(int, int)':
bitaro.cpp:21: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]
   21 |       for(; i < vec[u].size() && j < vec[v].size(); ) {
      |             ~~^~~~~~~~~~~~~~~
bitaro.cpp:21: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]
   21 |       for(; i < vec[u].size() && j < vec[v].size(); ) {
      |                                  ~~^~~~~~~~~~~~~~~
bitaro.cpp:31: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]
   31 |       while(i < vec[u].size()) {
      |             ~~^~~~~~~~~~~~~~~
bitaro.cpp:36: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]
   36 |       while(j < vec[v].size()) {
      |             ~~^~~~~~~~~~~~~~~

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