oj.uz

Submission #658775

# Submission time Handle Problem Language Result Execution time Memory
658775 2022-11-14T21:34:03 Z Dec0Dedd Link (CEOI06_link) C++14
100 / 100
 421 ms 48076 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12036 KB Output is correct
3 Correct 6 ms 12116 KB Output is correct
4 Correct 8 ms 12244 KB Output is correct
5 Correct 10 ms 12420 KB Output is correct
6 Correct 16 ms 14332 KB Output is correct
7 Correct 22 ms 14992 KB Output is correct
8 Correct 30 ms 16912 KB Output is correct
9 Correct 58 ms 21684 KB Output is correct
10 Correct 53 ms 20548 KB Output is correct
11 Correct 107 ms 41440 KB Output is correct
12 Correct 110 ms 21452 KB Output is correct
13 Correct 187 ms 31408 KB Output is correct
14 Correct 203 ms 33708 KB Output is correct
15 Correct 273 ms 41032 KB Output is correct
16 Correct 322 ms 46572 KB Output is correct
17 Correct 349 ms 45584 KB Output is correct
18 Correct 364 ms 42308 KB Output is correct
19 Correct 357 ms 43844 KB Output is correct
20 Correct 421 ms 44360 KB Output is correct
21 Correct 384 ms 47964 KB Output is correct
22 Correct 357 ms 47912 KB Output is correct
23 Correct 378 ms 47912 KB Output is correct
24 Correct 387 ms 48076 KB Output is correct
25 Correct 384 ms 48044 KB Output is correct