제출 #392548

#제출 시각아이디문제언어결과실행 시간메모리
392548patrikpavic2결혼 문제 (IZhO14_marriage)C++17
96 / 100
1596 ms3032 KiB
#include <cstdio> #include <cstring> #include <vector> #define PB push_back using namespace std; typedef long long ll; const int N = (1 << 15); int par[N], n, m, bio[N], k, un[N], cookie = 1; vector < int > v[N]; bool dodaj(int x){ if(bio[x] == cookie) return 0; bio[x] = cookie; for(int y : v[x]){ if(un[y] && par[y] == -1){ par[x] = y; par[y] = x; return 1; } } for(int y : v[x]){ if(un[y] && dodaj(par[y])){ par[x] = y; par[y] = x; return 1; } } return 0; } int main(){ scanf("%d%d%d", &n, &m, &k); for(int i = 0;i < k;i++){ int a, b; scanf("%d%d", &a, &b); a--; b--; v[a].PB(n + b), v[b + n].PB(a); } memset(par, -1, sizeof(par)); for(int i = 0;i < m;i++) un[i + n] = 1; int r = 0, sol = 0; ll ans = 0; for(int l = 0;l < n;l++){ if(l && sol == m){ un[l - 1] = 0; if(par[l - 1] != -1){ sol--; par[par[l - 1]] = -1; sol += dodaj(par[l - 1]); cookie++; } } while(r < n && sol < m){ un[r] = 1; sol += dodaj(r); cookie++; r++; } ans += (n + 1 - r) * (sol == m); } printf("%lld\n", ans); return 0; }

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

marriage.cpp: In function 'int main()':
marriage.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |  scanf("%d%d%d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:37:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |   int a, b; scanf("%d%d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...