oj.uz

Submission #658744

# Submission time Handle Problem Language Result Execution time Memory
658744 2022-11-14T19:53:13 Z Dec0Dedd Link (CEOI06_link) C++14
0 / 100
 414 ms 55112 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];

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11988 KB Output isn't correct
2 Incorrect 6 ms 12072 KB Output isn't correct
3 Incorrect 7 ms 12116 KB Output isn't correct
4 Incorrect 7 ms 12244 KB Output isn't correct
5 Incorrect 8 ms 12336 KB Output isn't correct
6 Incorrect 16 ms 14676 KB Output isn't correct
7 Incorrect 24 ms 15608 KB Output isn't correct
8 Incorrect 41 ms 17724 KB Output isn't correct
9 Incorrect 47 ms 23004 KB Output isn't correct
10 Incorrect 45 ms 21816 KB Output isn't correct
11 Incorrect 107 ms 43556 KB Output isn't correct
12 Incorrect 108 ms 24156 KB Output isn't correct
13 Incorrect 179 ms 34900 KB Output isn't correct
14 Incorrect 189 ms 37772 KB Output isn't correct
15 Incorrect 269 ms 45924 KB Output isn't correct
16 Incorrect 294 ms 51996 KB Output isn't correct
17 Incorrect 367 ms 51808 KB Output isn't correct
18 Incorrect 378 ms 49204 KB Output isn't correct
19 Incorrect 378 ms 50720 KB Output isn't correct
20 Incorrect 414 ms 51248 KB Output isn't correct
21 Incorrect 413 ms 55108 KB Output isn't correct
22 Incorrect 398 ms 54856 KB Output isn't correct
23 Incorrect 380 ms 54984 KB Output isn't correct
24 Incorrect 407 ms 54956 KB Output isn't correct
25 Incorrect 400 ms 55112 KB Output isn't correct