Submission #91407

#TimeUsernameProblemLanguageResultExecution timeMemory
91407mirbek01Marriage questions (IZhO14_marriage)C++11
94 / 100
1568 ms21360 KiB
# include <bits/stdc++.h> using namespace std; const int N = 1e5 + 2; int n, m, k, mt[N], used[N], ans, L, R, pt = 1; vector <int> g[N], vr, mr; bool dfs(int v){ if(used[v]) return 0; vr.push_back(v); used[v] = 1; for(int to : g[v]){ if(to < L) break; if(to <= n && to > R) continue; if(mt[to] == -1 || dfs(mt[to])){ mt[to] = v; mt[v] = to; return true; } } return false; } bool check(){ while(!mr.empty()){ int v = mr.back(); if(mt[v] == -1){ for(int i = 0; i < vr.size(); i ++){ used[vr[i]] = 0; } if(!dfs(v)) return false; } mr.pop_back(); } return mr.empty(); } int main(){ scanf("%d %d %d", &n, &m, &k); for(int i = 1; i <= k; i ++){ int a, b; scanf("%d %d", &a, &b); g[a].push_back(b + n); g[b + n].push_back(a); } for(int i = n + 1; i <= n + m; i ++) sort(g[i].rbegin(), g[i].rend()); memset(mt, -1, sizeof(mt)); for(int i = n + 1; i <= n + m; i ++) mr.push_back(i); for(int i = 1; i <= n; i ++){ L = i, R = pt; while(pt <= n && !check()) pt ++, R = pt; ans += n - pt + 1; if(mt[L] != -1){ mt[mt[L]] = -1; mr.push_back(mt[L]); } } printf("%d", ans); }

Compilation message (stderr)

marriage.cpp: In function 'bool check()':
marriage.cpp:32:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int i = 0; i < vr.size(); i ++){
                                  ~~^~~~~~~~~~~
marriage.cpp: In function 'int main()':
marriage.cpp:44:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d", &n, &m, &k);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:48:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...