Submission #91382

#TimeUsernameProblemLanguageResultExecution timeMemory
91382mirbek01Marriage questions (IZhO14_marriage)C++11
66 / 100
1580 ms13244 KiB
# include <bits/stdc++.h> using namespace std; const int N = 1e5 + 2; int n, m, k, mt[N], used[N], ans, L, R; 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 > R || to < L) && to <= n) continue; if(mt[to] == -1 || dfs(mt[to])){ if(mt[to] == -1) mr.push_back(to); if(mt[v] == -1) mr.push_back(v); mt[to] = v; mt[v] = to; return true; } } return false; } bool check(){ if(mt[L] == -1) return true; for(int i = n + 1; i <= n + m; i ++){ if(mt[i] == -1){ if(!dfs(i)){ for(int j = 0; j < (int)vr.size(); j ++) used[vr[j]] = 0; return false; } for(int j = 0; j < (int)vr.size(); j ++) used[vr[j]] = 0; } } return true; } bool ok(){ for(int i = 0; i < (int)mr.size(); i ++) mt[ mr[i] ] = -1; mr.clear(); for(int i = n + 1; i <= n + m; i ++){ for(int j = 0; j < (int)vr.size(); j ++){ used[ vr[j] ] = 0; } vr.clear(); dfs(i); } for(int i = n + 1; i <= n + m; i ++){ if(mt[i] == -1) return false; } return true; } 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 = 1; i <= n + m; i ++){ sort(g[i].begin(), g[i].end()); } memset(mt, -1, sizeof(mt)); int lo = 1, hi = n, pos = -1; L = 1; while(hi - lo > 1){ int md = (lo + hi) >> 1; R = md; if(ok()) hi = md - 1, pos = md; else lo = md + 1; } if(pos == -1){ cout << 0 << endl; return 0; } ans += n - pos + 1; if(mt[L] != -1){ mt[mt[L]] = -1; } memset(used, 0, sizeof(used)); int pt = pos; for(int i = 2; i <= n - m + 1; i ++){ int lo = 1, hi = i; L = i, R = pt; while(pt <= n && !check()) pt ++, R = pt; ans += n - pt + 1; if(mt[L] != -1){ mt[mt[L]] = -1; } } printf("%d", ans); }

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:111:17: warning: unused variable 'lo' [-Wunused-variable]
             int lo = 1, hi = i;
                 ^~
marriage.cpp:111:25: warning: unused variable 'hi' [-Wunused-variable]
             int lo = 1, hi = i;
                         ^~
marriage.cpp:67: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:71: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...