Submission #91515

#TimeUsernameProblemLanguageResultExecution timeMemory
91515mirbek01Marriage questions (IZhO14_marriage)C++11
100 / 100
271 ms4120 KiB
# include <bits/stdc++.h> using namespace std; const int N = 33002; int n, m, k, mt[N], cnt, used[N], ans, L, R, pt = 1; vector <int> g[N], gr[N], mr; bool dfs(int v){ if(used[v] == cnt) return 0; used[v] = cnt; for(int i = (int)g[v].size() - 1; i >= 0; i --){ int to = g[v][i]; if(to < L) break; 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){ cnt ++; 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); gr[a].push_back(b + n); } memset(mt, -1, sizeof(mt)); for(int i = n + 1; i <= n + m; i ++) mr.push_back(i); for(int j = 0; j < gr[1].size(); j ++){ int v = gr[1][j]; g[v].push_back(1); } for(int i = 1; i <= n; i ++){ L = i, R = pt; while(pt <= n && !check()){ pt ++, R = pt; for(int j = 0; j < gr[pt].size(); j ++){ int v = gr[pt][j]; g[v].push_back(pt); } } ans += n - pt + 1; if(mt[L] != -1){ mr.push_back(mt[L]); mt[mt[L]] = -1; } } printf("%d", ans); }

Compilation message (stderr)

marriage.cpp: In function 'int main()':
marriage.cpp:53:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = 0; j < gr[1].size(); j ++){
                      ~~^~~~~~~~~~~~~~
marriage.cpp:62:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int j = 0; j < gr[pt].size(); j ++){
                                  ~~^~~~~~~~~~~~~~~
marriage.cpp:40: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:44: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...