oj.uz

Submission #584025

# Submission time Handle Problem Language Result Execution time Memory
584025 2022-06-26T16:43:07 Z Sam_a17 Link (CEOI06_link) C++14
44 / 100
 357 ms 34072 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;

#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif

#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt __builtin_popcount

#define pb push_back
#define popf pop_front
#define popb pop_back
#define ld long double
#define ll long long

void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
void print(long double t) {cerr << t;}

template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T> void print(T v[],T n) {cerr << "["; for(int i = 0; i < n; i++) {cerr << v[i] << " ";} cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'

// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};

// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();

  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}

// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 5e5 + 10, inf = 1e9;
int n, k, in[N], dist[N], answ;
vector<int> adj[N];
bool used[N];

int cycle(int node) {
  // dbg(node)
  int cur = node;
  vector<int> path;
  while(!used[cur]) {
    used[cur] = true;
    path.push_back(cur);
    cur = adj[cur][0];
  }

  // dbg(path)

  // dbg(sz(path))

  for(auto i: path) {
    used[i] = false;
  }

  {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > q;

    for(auto i: path) {
      q.push({dist[i], i});
    }

    while(!q.empty()) {
      auto u = q.top();
      q.pop();
      if(used[u.second]) {
        continue;
      }
      used[u.second] = true;

      if(u.first >= k) {
        break;
      }

      for(auto i: adj[u.second]) {
        if(dist[i] > dist[u.second] + 1) {
          dist[i] = dist[u.second] + 1;
          q.push({dist[i], i});
        }
      }
    }
  }
  
  int m = sz(path);

  int mini = 0;
  for(int i = 0; i < m; i++) {
    if(dist[path[i]] == inf) {
      ++mini;
    }
  }

  if(!mini) {
    for(auto i: path) {
      used[i] = true;
    }
    return 0;
  }

  int lst = -1;
  vector<int> ptr(m, 0);
  for(int i = 2 * m - 1; i >= 0; i--) {
    if(dist[path[i % m]] == inf) {
      lst = i % m;
      ptr[lst] = lst;
    } else if(lst != -1) {
      ptr[i % m] = lst;
    }
  }

  for(int i = 0; i < m; i++) {
    assert(ptr[i] != -1);
  }

  for(int start = 0; start < min(k, m); start++) {
    int road = 0, pos = start, ansi = 0;
    while(true) {
      if(ptr[pos] < pos) {
        road += ptr[pos];
        road += m - ptr[pos];
      } else {
        road += ptr[pos] - pos;
      }
      pos = ptr[pos];
      
      if(road >= m) {
        break;
      }

      ansi++, road += k;
      pos += k, pos %= m;
    }

    mini = min(mini, ansi);
  }

  //
  for(auto i: path) {
    used[i] = true;
  }

  return mini;
}

void solve_() {
  cin >> n >> k;
  for(int i = 1; i <= n; i++) {
    int a, b; cin >> a >> b;
    adj[a].push_back(b); in[b]++;
  }

  for(int i = 2; i <= n; i++) {
    if(!in[i]) {
      adj[1].push_back(i);
      in[i]++;
      answ++;
    }
  }

  {
    for(int i = 1; i <= n; i++) {
      dist[i] = inf;
    }

    queue<pair<int, int>> q;
    q.push({1, 0});
    used[1] = true;

    while(!q.empty()) {
      auto u = q.front();
      q.pop();

      int curr = u.second + 1;
      if(curr > k) {
        answ++, curr = 1;
      }

      for(auto i: adj[u.first]) {
        
        dist[i] = min(dist[i], curr);
        in[i]--;
        if(!in[i] && !used[i]) {
          used[i] = true;
          q.push({i, dist[i]}); 
        }
      }
    }
  }

  for(int i = 1; i <= n; i++) {
    if(!used[i]) {
      // we get cycle
      answ += cycle(i);
    }
  }


  printf("%d\n", answ);
}

int main () {
  setIO("");

  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };

  int test_cases = 1;
  solve(test_cases);

  return 0;
}

Compilation message

link.cpp: In function 'void setIO(std::string)':
link.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
link.cpp:66:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
44.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Incorrect 6 ms 11988 KB Output isn't correct
3 Incorrect 6 ms 12116 KB Output isn't correct
4 Incorrect 7 ms 12204 KB Output isn't correct
5 Incorrect 7 ms 12308 KB Output isn't correct
6 Correct 15 ms 13328 KB Output is correct
7 Incorrect 20 ms 14108 KB Output isn't correct
8 Correct 26 ms 15016 KB Output is correct
9 Incorrect 38 ms 16560 KB Output isn't correct
10 Correct 38 ms 16472 KB Output is correct
11 Incorrect 66 ms 19652 KB Output isn't correct
12 Incorrect 99 ms 20244 KB Output isn't correct
13 Correct 177 ms 22948 KB Output is correct
14 Correct 161 ms 24884 KB Output is correct
15 Correct 216 ms 27640 KB Output is correct
16 Incorrect 272 ms 29584 KB Output isn't correct
17 Correct 288 ms 32036 KB Output is correct
18 Incorrect 355 ms 33172 KB Output isn't correct
19 Incorrect 339 ms 33304 KB Output isn't correct
20 Incorrect 330 ms 33292 KB Output isn't correct
21 Correct 357 ms 33524 KB Output is correct
22 Correct 333 ms 34004 KB Output is correct
23 Incorrect 349 ms 33596 KB Output isn't correct
24 Correct 327 ms 34040 KB Output is correct
25 Incorrect 338 ms 34072 KB Output isn't correct