Submission #852750

#	Time	Username	Problem	Language	Result	Execution time	Memory
852750		gun_gan	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	27 ms	16516 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], r[MX];
int dist[MX], deg[MX];
bool vis[MX];
priority_queue<pair<int,int>> pq[MX];
vector<pair<int,int>> vec[MX];

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]++;
            r[v].push_back(u);
      }

      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(pq[v].size() < B) pq[v].push({0, v}); 

            while(!pq[v].empty()) {
                  vec[v].push_back(pq[v].top());
                  pq[v].pop();
            }

            for(auto u : g[v]) {
                  for(auto [y, x] : vec[v]) {
                        pq[u].push({y + 1, x});
                        if(pq[u].size() > B) pq[u].pop();
                  }

                  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]) {
                        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;
                  }
                  for(int i = 1; i <= N; i++) {
                        for(auto k : r[i]) deg[k]++;
                  }

                  for(int i = 0; i < yj; i++) {
                        int x;
                        cin >> x;
                        vis[x] = 1;
                  }

                  queue<int> q;
                  if(!vis[tj]) {
                        q.push(tj);
                        dist[tj] = 0;
                  }

                  int res = -1;
                  while(!q.empty()) {
                        auto v = q.front(); q.pop();
                        if(!vis[v]) res = max(res, dist[v]);
                        for(auto u : r[v]) {
                              deg[u]--;
                              dist[u] = max(dist[u], dist[v] + 1);
                              if(!deg[u]) 
                                    q.push(u);
                        }
                  }

                  cout << res << '\n';

                  memset(vis, 0, sizeof vis);
            }
            
      }


}

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