제출 #128473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128473		letrongdat	결혼 문제 (IZhO14_marriage)	C++17	84 / 100	251 ms	1144 KiB

marriage

#include <bits/stdc++.h>
using namespace std;
#define forn(i, a, b)           for(int i=a; i<=b; ++i)
const int maxN = 3e4 +10;
const int maxM = 2e3 +10;
int matched[maxN];
vector<int> E[maxM];
int le, ri, t = 1;
int N, M, K;
long long result;
int visited[maxM];
vector<int> not_match;
bool visit(int u) {
    if (visited[u] == t) return false;
    visited[u] = t;
    while (E[u].size() && E[u].back() < le) E[u].pop_back();
    for(int i=0; i<E[u].size(); ++i) {
        int v = E[u][i];
        if (v <= ri) {
            if (!matched[v] || visit(matched[v])) {
                matched[v] = u;
                return true;
            }
        }    
    }
    return false;
}
int main() {
    ios::sync_with_stdio(0);
    cin >> N >> M >> K;
    forn(i, 1, K) {
        int Ai, Bi; 
        cin >> Ai >> Bi;
        E[Bi].push_back(Ai);
    }
    forn(i, 1, M) {
        sort(E[i].begin(), E[i].end());
        reverse(E[i].begin(), E[i].end());
    }
    forn(i, 1, M) not_match.push_back(i);
    for(le = 1; le <= N; ++le) {
        if (matched[le-1]) {
            not_match.push_back(matched[le-1]);
            matched[le-1] = 0;
        }
        while (ri < N && not_match.size()) {
            ri ++;
            while (not_match.size()) {
                t ++;
                if (visit(not_match.back())) not_match.pop_back(); else break;
            }
        }
        if (not_match.empty()) result += N-ri+1;
    }
    cout << result;
}

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

marriage.cpp: In function 'bool visit(int)':
marriage.cpp:17:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<E[u].size(); ++i) {
                  ~^~~~~~~~~~~~

• Subtask 1: 84 / 100