Submission #516017

#TimeUsernameProblemLanguageResultExecution timeMemory
516017Be_dosMarriage questions (IZhO14_marriage)C++17
56 / 100
1598 ms1052 KiB
#include <iostream> #include <cmath> #include <cctype> #include <vector> #include <algorithm> #include <set> #include <map> #include <deque> #include <stack> #include <unordered_set> #include <sstream> #include <cstring> #include <iomanip> #include <queue> #include <unordered_map> #include <random> #include <cfloat> #include <chrono> #include <bitset> #include <complex> #include <immintrin.h> #include <cassert> bool try_kuhn(int32_t v, bool* vis, std::vector<int32_t>* graph, int32_t* matched, int32_t left, int32_t right) { vis[v] = true; for(int32_t i = 0; i < graph[v].size(); i++) if(graph[v][i] >= left && graph[v][i] <= right && matched[graph[v][i]] == -1) { matched[graph[v][i]] = v; return true; } for(int32_t i = 0; i < graph[v].size(); i++) if(graph[v][i] >= left && graph[v][i] <= right && !vis[matched[graph[v][i]]] && try_kuhn(matched[graph[v][i]], vis, graph, matched, left, right)) { matched[graph[v][i]] = v; return true; } return false; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int32_t n, m, k; std::cin >> n >> m >> k; assert(m > 2); std::vector<int32_t>* graph = new std::vector<int32_t>[m]; for(int32_t i = 0; i < k; i++) { int32_t src, dst; std::cin >> src >> dst; src--; dst--; //int32_t src = rand() % n, dst = rand() % m; graph[dst].push_back(src); } bool* vis = new bool[m]; int32_t* matched = new int32_t[n]; int32_t matched_cnt = 0; for(int32_t i = 0; i < n; i++) matched[i] = -1; int32_t right_ptr = -1; int32_t ans = 0; for(int32_t i = 0; i < n; i++) { //int32_t rematched = -1; if(i > 0 && matched[i - 1] != -1) { matched_cnt--; //rematched = matched[i - 1]; } //if(rematched != -1) { while(right_ptr < n - 1 && matched_cnt < m) { right_ptr++; matched_cnt = 0; for(int32_t p = 0; p < n; p++) matched[p] = -1; for(int32_t p = 0; p < m; p++) { for(int32_t j = 0; j < m; j++) vis[j] = false; if(try_kuhn(p, vis, graph, matched, i, right_ptr)) matched_cnt++; } } //} if(matched_cnt < m) break; ans += n - right_ptr; } std::cout << ans << "\n"; return 0; }

Compilation message (stderr)

marriage.cpp: In function 'bool try_kuhn(int32_t, bool*, std::vector<int>*, int32_t*, int32_t, int32_t)':
marriage.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int32_t i = 0; i < graph[v].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~~
marriage.cpp:31:26: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int32_t i = 0; i < graph[v].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...