Submission #345254

#TimeUsernameProblemLanguageResultExecution timeMemory
345254maskoffMarriage questions (IZhO14_marriage)C++14
86 / 100
1582 ms25436 KiB
#include <bits/stdc++.h> #define file "" #define all(x) x.begin(), x.end() #define sc second #define fr first #define pb push_back #define mp make_pair using namespace std; typedef long long ll; typedef pair<int, int> pii; const ll inf = 1e18 + 5; const ll mod = 1e9 + 7; const int N = 5e5 + 5; int dx[] = {+1, 0, -1, 0}; int dy[] = {0, +1, 0, -1}; int n, m, k, timer; int used[N], mt[N], pr[N]; vector<int> g[N], all[N]; bool go(int v) { if (used[v] == timer) return false; used[v] = timer; for (int to : g[v]) if (mt[to] == false) { mt[to] = v; pr[v] = to; return true; } for (int to : g[v]) if (go(mt[to])) { mt[to] = v; pr[v] = to; return true; } return false; } bool check(int y, int p) { fill (pr + 1, pr + 1 + m, false); for (int i = 1; i <= m; i++) g[i].clear(); for (int i = y; i <= p; i++) { for (int j : all[i]) g[j].pb(i); } for (int i = 1; i <= m; i++) { timer++; go(i); } int ok = true; for (int i = 1; i <= m; i++) if (pr[i] == 0) ok = false; else mt[pr[i]] = false; return ok; } int main() { ios_base :: sync_with_stdio(false); cin.tie(nullptr); srand(time(nullptr)); cin >> n >> m >> k; for (int x, y, i = 1; i <= k; i++) { cin >> x >> y; all[x].pb(y); } ll res = 0; for (int i = 1; i <= n; i++) { int l = i + m - 1; int r = n; int ans = -1; while (l <= r) { int mid = l + r >> 1; if (check(i, mid)) ans = mid, r = mid - 1; else l = mid + 1; } if (ans == -1) break; else res += (n - ans + 1); } cout << res; return 0; }

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:81:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |     int mid = l + r >> 1;
      |               ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...