제출 #91392

#제출 시각아이디문제언어결과실행 시간메모리
91392mirbek01Marriage questions (IZhO14_marriage)C++11
78 / 100
1578 ms14272 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 <= n && (to > R || to < L)) continue; if(mt[to] == -1 || dfs(mt[to])){ mt[to] = v; mt[v] = to; return true; } } return false; } bool check(){ if(mt[L] == -1) return true; 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)){ break; } } mr.pop_back(); } return mr.empty(); } bool ok(){ for(int i = n + 1; i <= n + m; i ++){ if(mt[i] != -1){ mt[ mt[i] ] = -1; mt[i] = -1; } } 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 + 1; L = 1; while(lo < hi){ int md = (lo + hi) >> 1; R = md; if(ok()) hi = md; else lo = md + 1; } if(lo > n){ cout << 0 << endl; return 0; } ans += n - lo + 1; R = lo; ok(); if(mt[L] != -1){ mt[mt[L]] = -1; mr.push_back(mt[L]); } int pt = lo; for(int i = 2; 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); }

컴파일 시 표준 에러 (stderr) 메시지

marriage.cpp: In function 'bool check()':
marriage.cpp:33: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: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...