Submission #658775

#	Time	Username	Problem	Language	Result	Execution time	Memory
658775		Dec0Dedd	Link (CEOI06_link)	C++14	100 / 100	421 ms	48076 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];

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) {
   assert(r >= l);
   assert(pref[r]-pref[l] >= 0);
   return pref[r]-pref[l];
}

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

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

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

         if (que(i+1, nxt+1) <= k-1) break;
         i=nxt; ++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);
      ++indeg[b];
   }

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

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

   while (!q.empty()) {
      int v=q.front(); q.pop();
      if (d[v] > k) d[v]=1, ++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] == 2 || d[i] <= k) continue;
      dfs(i); pref[0]=0;

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

      if (x.empty()) {
         tmp.clear();
         continue;
      }

      int h=x.size();
      for (int p=0; p<h; ++p) x.push_back(x[p]+(int)tmp.size());

      pref[1]=x[0];
      for (int j=2; j<=(int)x.size(); ++j) {
         assert(x[j-1]-x[j-2] >= 0);
         pref[j]=pref[j-1]+x[j-1]-x[j-2];
      }

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

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

• Subtask 1: 100 / 100