Submission #852762

#	Time	Username	Problem	Language	Result	Execution time	Memory
852762		gun_gan	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2021 ms	17360 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 [y, x] : vec[u]) vec[v].push_back({y + 1, x});
      sort(vec[v].rbegin(), vec[v].rend());
      vec[v].resize(unique(vec[v].begin(), vec[v].end()) - vec[v].begin());
      while(vec[v].size() > B) vec[v].pop_back();
}

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';
            }
            
      }


}

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