oj.uz

Submission #584050

# Submission time Handle Problem Language Result Execution time Memory
584050 2022-06-26T17:14:25 Z Sam_a17 Link (CEOI06_link) C++14
52 / 100
 912 ms 68116 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;
  }

  dbg("done")

  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 {
      assert(lst != -1);
      ptr[i % m] = lst;
    }
  }

  // dbg(ptr)

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

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

    // assert(false);
    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});
    dist[1] = 0;
    used[1] = true;

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

      // dbg(u)
      if(u.second > k) {
        dist[u.first] = 1;
        answ++;
      }

      for(auto i: adj[u.first]) {
        in[i]--;
        dist[i] = min(dist[i], dist[u.first] + 1);

        if(!in[i]) {
          used[i] = true;
          q.push({i, dist[i]}); 
        }
      }
    }
  }

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

  // dbg(answ)

  for(int i = 1; i <= n; i++) {
    if(!used[i]) {
      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
52.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 12144 KB Output is correct
4 Runtime error 18 ms 24664 KB Execution killed with signal 6
5 Runtime error 18 ms 24788 KB Execution killed with signal 6
6 Runtime error 33 ms 27248 KB Execution killed with signal 6
7 Runtime error 56 ms 28784 KB Execution killed with signal 6
8 Correct 69 ms 15368 KB Output is correct
9 Runtime error 200 ms 33836 KB Execution killed with signal 6
10 Correct 69 ms 16972 KB Output is correct
11 Runtime error 171 ms 38240 KB Execution killed with signal 6
12 Runtime error 145 ms 41164 KB Execution killed with signal 6
13 Correct 313 ms 23692 KB Output is correct
14 Correct 193 ms 25476 KB Output is correct
15 Correct 521 ms 28516 KB Output is correct
16 Correct 257 ms 30180 KB Output is correct
17 Correct 799 ms 33224 KB Output is correct
18 Runtime error 359 ms 65740 KB Execution killed with signal 6
19 Runtime error 438 ms 66944 KB Execution killed with signal 6
20 Runtime error 634 ms 67948 KB Execution killed with signal 6
21 Correct 596 ms 34628 KB Output is correct
22 Correct 892 ms 35304 KB Output is correct
23 Runtime error 475 ms 67944 KB Execution killed with signal 6
24 Correct 912 ms 35448 KB Output is correct
25 Runtime error 480 ms 68116 KB Execution killed with signal 6