제출 #392597

#제출 시각아이디문제언어결과실행 시간메모리
392597patrikpavic2결혼 문제 (IZhO14_marriage)C++17
96 / 100
1599 ms5220 KiB
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #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; int poc[N], deg[N]; vector < int > v[N], m1[N]; bool dodaj(int x){ if(bio[x] == cookie) return 0; bio[x] = cookie; while((int)m1[x].size() > 0 && (!un[m1[x].back()] || par[m1[x].back()] != -1)) m1[x].pop_back(); if((int)m1[x].size() > 0){ int y = m1[x].back(); par[x] = y; par[y] = x; m1[x].pop_back(); return 1; } for(int i = poc[x];i < deg[x] && un[v[x][i]];i++){ if(par[v[x][i]] == -1) { printf("wtf.."); exit(0); } if(dodaj(par[v[x][i]])){ par[x] = v[x][i]; par[v[x][i]] = 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); deg[a]++; deg[n + b]++; } memset(par, -1, sizeof(par)); for(int i = 0;i < m;i++){ un[i + n] = 1; sort(v[i + n].begin(), v[i + n].end()); for(int x : v[i + n]) m1[x].PB(i + n); } int r = 0, sol = 0; ll ans = 0; for(int l = 0;l < n;l++){ if(l && sol == m){ un[l - 1] = 0; for(int i = n;i < m + n;i++) if(poc[i] < deg[i] && v[i][poc[i]] < l) poc[i]++; if(par[l - 1] != -1){ sol--; par[par[l - 1]] = -1; sol += dodaj(par[l - 1]); cookie++; if(par[par[l - 1]] == -1){ int cnt = 0; for(int x : v[par[l - 1]]) { if(x < l) continue; cnt++; m1[x].PB(par[l - 1]); if(cnt > m) break; } } } } while(r < n && sol < m){ un[r] = 1; sol += dodaj(r); cookie++; if(par[r] == -1){ for(int x : v[r]) m1[x].PB(r); } r++; } ans += (n + 1 - r) * (sol == m); } printf("%lld\n", ans); return 0; }

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

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