Submission #658744

#	Time	Username	Problem	Language	Result	Execution time	Memory
658744		Dec0Dedd	Link (CEOI06_link)	C++14	0 / 100	414 ms	55112 KiB

link

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define pii pair<int, int>

const int N = 5e5+1;
const int INF = 1e9+1;

int n, k, indeg[N], d[N], ans=0;
vector<int> G[N];
ll pref[N];

bool rm[N];
int vis[N];

vector<int> tmp;
void dfs(int v) {
   ++vis[v];
   if (vis[v] == 1) tmp.push_back(v);

   for (auto u : G[v]) {
      if (vis[u] == 2) continue;
      d[u]=min(d[u], d[v]+1);
      dfs(u);
   }
}

int que(int l, int r) {
   if (l > r) swap(l, r);
   return pref[r]-pref[l-1];
}

int calc(vector<ll> x) {
   if (x.empty()) return 0;
   int s=0, i, tmp, n=x.size()/2, res=INF;

   while (que(1, s+1) <= k && s < n) {
      i=s, tmp=1;

      while (i <= s+n-1) {
         int l=i+1, r=s+n-1, nxt=i+1;
         while (l <= r) {
            int m=(l+r)/2;
            if (que(i+1, m+1) > k) nxt=m, r=m-1;
            else r=m-1;
         }

         if (k > s+n-1) break;
         i=nxt; ++tmp;
      }

      return tmp;
      res=min(res, tmp);
      ++s;
   }

   return res;
}

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);
   cout.tie(NULL);
   
   cin>>n>>k;
   for (int i=1; i<=n; ++i) {
      int a, b; cin>>a>>b;
      G[a].push_back(b);
   }

   for (int i=0; i<=n; ++i) d[i]=INF;
   d[1]=0;

   queue<int> q;
   for (int i=1; i<=n; ++i) {
      for (auto u : G[i]) ++indeg[u];
   }

   for (int i=1; i<=n; ++i) {
      if (indeg[i] == 0) q.push(i);
   }

   while (!q.empty()) {
      int v=q.front(); q.pop();
      rm[v]=true;
      if (d[v] > k) d[v]=0, ++ans;

      for (auto u : G[v]) {
         d[u]=min(d[u], d[v]+1);
         --indeg[u];
         if (indeg[u] == 0) q.push(u);
      }
   } assert(q.empty());

   vector<ll> x;
   for (int i=1; i<=n; ++i) {
      if (vis[i] || rm[i] || d[i] <= k) continue;
      dfs(i); pref[0]=0;

      int sz=tmp.size();
      for (int i=1; i<=sz; ++i) {
         pref[i]=pref[i-1];
         if (rm[tmp[i-1]] || d[tmp[i-1]] <= k) continue;
         else x.push_back(i-1);
      }

      x.insert(x.end(), x.begin(), x.end());
      if (!x.empty()) pref[1]=x[0];
      for (int i=2; i<=(int)x.size(); ++i) {
         pref[i]=pref[i-1]+x[i-1]-x[i-2];
      }

      ans+=calc(x);
      tmp.clear(), x.clear();
   }

   cout<<ans<<"\n";
}

• Subtask 1: 0 / 100