oj.uz

답안 #711612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
711612 2023-03-17T09:47:37 Z Sam_a17 결혼 문제 (IZhO14_marriage) C++17
54 / 100
 324 ms 6472 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
54.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Runtime error 2 ms 2772 KB Execution killed with signal 11
3 Runtime error 2 ms 2772 KB Execution killed with signal 11
4 Runtime error 2 ms 2772 KB Execution killed with signal 11
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 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 Runtime error 2 ms 2772 KB Execution killed with signal 11
14 Correct 1 ms 1492 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Runtime error 2 ms 2816 KB Execution killed with signal 11
17 Correct 1 ms 1492 KB Output is correct
18 Correct 1 ms 1492 KB Output is correct
19 Correct 2 ms 1492 KB Output is correct
20 Correct 1 ms 1492 KB Output is correct
21 Correct 1 ms 1492 KB Output is correct
22 Runtime error 3 ms 2772 KB Execution killed with signal 11
23 Correct 1 ms 1492 KB Output is correct
24 Correct 1 ms 1492 KB Output is correct
25 Correct 15 ms 1696 KB Output is correct
26 Runtime error 4 ms 2932 KB Execution killed with signal 11
27 Correct 1 ms 1492 KB Output is correct
28 Runtime error 3 ms 2836 KB Execution killed with signal 11
29 Runtime error 4 ms 3028 KB Execution killed with signal 11
30 Runtime error 3 ms 3028 KB Execution killed with signal 11
31 Correct 99 ms 2112 KB Output is correct
32 Runtime error 7 ms 3028 KB Execution killed with signal 11
33 Correct 1 ms 1492 KB Output is correct
34 Runtime error 14 ms 2900 KB Execution killed with signal 11
35 Correct 57 ms 2596 KB Output is correct
36 Correct 42 ms 2484 KB Output is correct
37 Correct 324 ms 2244 KB Output is correct
38 Correct 17 ms 2756 KB Output is correct
39 Runtime error 241 ms 3448 KB Execution killed with signal 11
40 Correct 5 ms 1748 KB Output is correct
41 Runtime error 10 ms 3796 KB Execution killed with signal 11
42 Runtime error 8 ms 4052 KB Execution killed with signal 11
43 Runtime error 12 ms 4304 KB Execution killed with signal 11
44 Runtime error 22 ms 5284 KB Execution killed with signal 11
45 Runtime error 14 ms 4688 KB Execution killed with signal 11
46 Runtime error 44 ms 6172 KB Execution killed with signal 11
47 Runtime error 31 ms 5936 KB Execution killed with signal 11
48 Runtime error 23 ms 5844 KB Execution killed with signal 11
49 Runtime error 58 ms 6472 KB Execution killed with signal 11
50 Runtime error 242 ms 3604 KB Execution killed with signal 11