oj.uz

Submission #711613

# Submission time Handle Problem Language Result Execution time Memory
711613 2023-03-17T09:48:52 Z Sam_a17 Marriage questions (IZhO14_marriage) C++17
22 / 100
 248 ms 3228 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(x) __builtin_popcount(x)

#define pb push_back
#define popf pop_front
#define popb pop_back

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(long double t) {cerr << t;}
void print(unsigned long long 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, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } 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 = 5e4 + 10;
vector<int> adj[N];
int n, m, k, mt[N];
bool used[N];

int khun(int node, int lim_down, int lim_up) {
  if(used[node]) {
    return false;
  }
  used[node] = true;
  for(auto i: adj[node]) {
    
    if(i > lim_up) {
      break;
    }
    
    if(i < lim_down) {
      continue;
    }

    if(mt[i] == -1 || khun(mt[i], lim_down, lim_up)) {
      mt[i] = node;
      return true;
    }
  }
  return false;
}

void solve_() {
  cin >> n >> m >> k;

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

  for(int i = 1; i <= m; i++) {
    sort(all(adj[i]));
  }

  int ina = m, inb = n, ans = -1;
  while(ina <= inb) {
    int mid = (ina + inb) / 2;
    
    int cnt = 0;
    for(int i = 1; i <= mid; i++) {
      mt[i + m] = -1;
    }

    for(int i = 1; i <= m; i++) {
      for(int j = 1; j <= m; j++) {
        used[j] = false;
      }
      cnt += khun(i, 0, mid + m);
    }

    if(cnt == m) {
      ans = mid;
      inb = mid - 1;
    } else {
      ina = mid + 1;
    }
  }

  if(ans == -1) {
    cout << 0 << endl;
    return;
  }


  {
    for(int i = 1; i <= n; i++) {
      mt[i + m] = -1;
    }

    for(int i = 1; i <= m; i++) {
      for(int j = 1; j <= m; j++) {
        used[j] = false;
      }
      khun(i, 0, ans + m);
    }
  }

  int answ = n - ans + 1;

  // int r = ans;
  // for(int i = 1; i <= n; i++) {
  //   if(mt[i] == -1) {
  //     answ += n - r + 1;
  //     continue;
  //   }

  //   int who = mt[i + m];
  //   while(r <= n) {
  //     for(int j = 1; j <= m; j++) {
  //       used[j] = false;
  //     }
  //     int c = khun(who, i + m + 1, r + m);
  //     if(c) break;
  //     r++;
  //   }

  //   //
  //   if(r <= n) {
  //     answ += n - r + 1;
  //   } else {
  //     break;
  //   }
  // }

  cout << answ << endl;
}

int main() {
  setIO();

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

  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);

  return 0;
}

Compilation message

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

Subtask #1
22.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1492 KB Output isn't correct
2 Incorrect 1 ms 1492 KB Output isn't correct
3 Incorrect 1 ms 1492 KB Output isn't correct
4 Incorrect 2 ms 1492 KB Output isn't correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1412 KB Output is correct
7 Incorrect 2 ms 1492 KB Output isn't correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 2 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Incorrect 1 ms 1492 KB Output isn't correct
14 Incorrect 2 ms 1492 KB Output isn't correct
15 Incorrect 1 ms 1492 KB Output isn't correct
16 Incorrect 1 ms 1492 KB Output isn't correct
17 Incorrect 1 ms 1492 KB Output isn't correct
18 Incorrect 1 ms 1492 KB Output isn't correct
19 Incorrect 2 ms 1492 KB Output isn't correct
20 Incorrect 1 ms 1492 KB Output isn't correct
21 Correct 1 ms 1492 KB Output is correct
22 Incorrect 1 ms 1492 KB Output isn't correct
23 Incorrect 2 ms 1492 KB Output isn't correct
24 Incorrect 1 ms 1492 KB Output isn't correct
25 Incorrect 5 ms 1616 KB Output isn't correct
26 Incorrect 2 ms 1492 KB Output isn't correct
27 Correct 1 ms 1492 KB Output is correct
28 Incorrect 1 ms 1492 KB Output isn't correct
29 Incorrect 3 ms 1620 KB Output isn't correct
30 Incorrect 2 ms 1492 KB Output isn't correct
31 Incorrect 52 ms 2104 KB Output isn't correct
32 Incorrect 5 ms 1620 KB Output isn't correct
33 Correct 1 ms 1492 KB Output is correct
34 Incorrect 13 ms 1572 KB Output isn't correct
35 Incorrect 15 ms 2480 KB Output isn't correct
36 Incorrect 12 ms 2472 KB Output isn't correct
37 Incorrect 121 ms 2232 KB Output isn't correct
38 Incorrect 21 ms 2712 KB Output isn't correct
39 Incorrect 248 ms 1792 KB Output isn't correct
40 Correct 6 ms 1748 KB Output is correct
41 Incorrect 9 ms 1916 KB Output isn't correct
42 Incorrect 9 ms 2132 KB Output isn't correct
43 Incorrect 11 ms 2260 KB Output isn't correct
44 Incorrect 24 ms 2600 KB Output isn't correct
45 Incorrect 13 ms 2428 KB Output isn't correct
46 Incorrect 42 ms 3132 KB Output isn't correct
47 Incorrect 23 ms 3028 KB Output isn't correct
48 Incorrect 20 ms 2916 KB Output isn't correct
49 Incorrect 48 ms 3228 KB Output isn't correct
50 Incorrect 244 ms 1828 KB Output isn't correct