oj.uz

Submission #658769

# Submission time Handle Problem Language Result Execution time Memory
658769 2022-11-14T21:20:14 Z Dec0Dedd Link (CEOI06_link) C++14
96 / 100
 433 ms 51600 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 < 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
96.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12096 KB Output is correct
4 Correct 7 ms 12244 KB Output is correct
5 Incorrect 9 ms 12400 KB Output isn't correct
6 Correct 18 ms 14740 KB Output is correct
7 Correct 27 ms 15524 KB Output is correct
8 Correct 34 ms 17660 KB Output is correct
9 Correct 50 ms 22952 KB Output is correct
10 Correct 45 ms 21672 KB Output is correct
11 Correct 102 ms 43328 KB Output is correct
12 Correct 109 ms 23736 KB Output is correct
13 Correct 164 ms 33832 KB Output is correct
14 Correct 209 ms 35840 KB Output is correct
15 Correct 314 ms 43284 KB Output is correct
16 Correct 283 ms 48728 KB Output is correct
17 Correct 365 ms 47724 KB Output is correct
18 Correct 380 ms 44388 KB Output is correct
19 Correct 400 ms 45988 KB Output is correct
20 Correct 406 ms 46444 KB Output is correct
21 Correct 427 ms 51432 KB Output is correct
22 Correct 422 ms 50208 KB Output is correct
23 Correct 354 ms 51140 KB Output is correct
24 Correct 433 ms 51600 KB Output is correct
25 Correct 411 ms 51476 KB Output is correct