oj.uz

Submission #711606

# Submission time Handle Problem Language Result Execution time Memory
711606 2023-03-17T09:42:07 Z Sam_a17 Marriage questions (IZhO14_marriage) C++17
18 / 100
 224 ms 3776 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;
  }

  cout << 1 << 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
18.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1492 KB Output isn't correct
2 Incorrect 1 ms 1620 KB Output isn't correct
3 Incorrect 1 ms 1492 KB Output isn't correct
4 Incorrect 1 ms 1500 KB Output isn't correct
5 Incorrect 1 ms 1496 KB Output isn't correct
6 Incorrect 1 ms 1492 KB Output isn't correct
7 Incorrect 2 ms 1496 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 1 ms 1492 KB Output isn't correct
15 Incorrect 2 ms 1500 KB Output isn't correct
16 Incorrect 2 ms 1504 KB Output isn't correct
17 Incorrect 2 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 1500 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 1 ms 1492 KB Output isn't correct
24 Incorrect 2 ms 1492 KB Output isn't correct
25 Incorrect 5 ms 1768 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 2 ms 1516 KB Output isn't correct
29 Incorrect 3 ms 1640 KB Output isn't correct
30 Incorrect 2 ms 1620 KB Output isn't correct
31 Incorrect 44 ms 2476 KB Output isn't correct
32 Incorrect 5 ms 1620 KB Output isn't correct
33 Correct 1 ms 1496 KB Output is correct
34 Incorrect 12 ms 1620 KB Output isn't correct
35 Incorrect 16 ms 3168 KB Output isn't correct
36 Incorrect 13 ms 3088 KB Output isn't correct
37 Incorrect 110 ms 2776 KB Output isn't correct
38 Incorrect 19 ms 3308 KB Output isn't correct
39 Incorrect 221 ms 1884 KB Output isn't correct
40 Correct 6 ms 1876 KB Output is correct
41 Incorrect 11 ms 2148 KB Output isn't correct
42 Incorrect 9 ms 2388 KB Output isn't correct
43 Incorrect 11 ms 2628 KB Output isn't correct
44 Incorrect 20 ms 3308 KB Output isn't correct
45 Incorrect 11 ms 2724 KB Output isn't correct
46 Incorrect 44 ms 3756 KB Output isn't correct
47 Incorrect 23 ms 3648 KB Output isn't correct
48 Incorrect 22 ms 3608 KB Output isn't correct
49 Incorrect 54 ms 3776 KB Output isn't correct
50 Incorrect 224 ms 1868 KB Output isn't correct