oj.uz

Submission #658774

# Submission time Handle Problem Language Result Execution time Memory
658774 2022-11-14T21:31:09 Z Dec0Dedd Link (CEOI06_link) C++14
96 / 100
 1500 ms 50060 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 (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 7 ms 11988 KB Output is correct
2 Correct 7 ms 12080 KB Output is correct
3 Correct 7 ms 12116 KB Output is correct
4 Correct 10 ms 12296 KB Output is correct
5 Correct 8 ms 12344 KB Output is correct
6 Correct 20 ms 14656 KB Output is correct
7 Correct 22 ms 15572 KB Output is correct
8 Correct 33 ms 17684 KB Output is correct
9 Correct 46 ms 22828 KB Output is correct
10 Correct 59 ms 21592 KB Output is correct
11 Correct 129 ms 42512 KB Output is correct
12 Correct 107 ms 22676 KB Output is correct
13 Correct 156 ms 33372 KB Output is correct
14 Correct 427 ms 35684 KB Output is correct
15 Correct 267 ms 42996 KB Output is correct
16 Execution timed out 1544 ms 48440 KB Time limit exceeded
17 Correct 358 ms 47548 KB Output is correct
18 Correct 870 ms 44024 KB Output is correct
19 Correct 427 ms 45772 KB Output is correct
20 Correct 390 ms 46212 KB Output is correct
21 Correct 403 ms 49864 KB Output is correct
22 Correct 381 ms 49800 KB Output is correct
23 Correct 358 ms 49828 KB Output is correct
24 Correct 403 ms 50060 KB Output is correct
25 Correct 400 ms 49992 KB Output is correct