oj.uz

Submission #584032

# Submission time Handle Problem Language Result Execution time Memory
584032 2022-06-26T16:57:58 Z Sam_a17 Link (CEOI06_link) C++14
0 / 100
 372 ms 34288 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 start = 0; start < min(k, m); start++) {
    int road = 0, pos = start, ansi = 0;
    while(true) {
      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();

      // dbg(u)
      int curr = u.second + 1, need_to_add = 0;
      if(curr > k) {
        curr = 1;
        need_to_add |= 1;
      }

      for(auto i: adj[u.first]) {
        if(dist[i] > curr) {
          dist[i] = curr;
          answ += need_to_add;
          if(!in[i] && !used[i]) {
            used[i] = true;
            q.push({i, dist[i]}); 
          }
        }
        
        in[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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11988 KB Output isn't correct
2 Incorrect 7 ms 11988 KB Output isn't correct
3 Incorrect 6 ms 12084 KB Output isn't correct
4 Incorrect 7 ms 12116 KB Output isn't correct
5 Incorrect 8 ms 12304 KB Output isn't correct
6 Incorrect 16 ms 13364 KB Output isn't correct
7 Incorrect 27 ms 14196 KB Output isn't correct
8 Incorrect 40 ms 15036 KB Output isn't correct
9 Incorrect 49 ms 16648 KB Output isn't correct
10 Incorrect 40 ms 16512 KB Output isn't correct
11 Incorrect 73 ms 19736 KB Output isn't correct
12 Incorrect 106 ms 20196 KB Output isn't correct
13 Incorrect 131 ms 22972 KB Output isn't correct
14 Incorrect 212 ms 24848 KB Output isn't correct
15 Incorrect 208 ms 27596 KB Output isn't correct
16 Incorrect 250 ms 29668 KB Output isn't correct
17 Incorrect 333 ms 32088 KB Output isn't correct
18 Incorrect 347 ms 33164 KB Output isn't correct
19 Incorrect 365 ms 33284 KB Output isn't correct
20 Incorrect 317 ms 33348 KB Output isn't correct
21 Incorrect 361 ms 34152 KB Output isn't correct
22 Incorrect 330 ms 33608 KB Output isn't correct
23 Incorrect 349 ms 33520 KB Output isn't correct
24 Incorrect 372 ms 34268 KB Output isn't correct
25 Incorrect 324 ms 34288 KB Output isn't correct