oj.uz

Submission #128471

# Submission time Handle Problem Language Result Execution time Memory
128471 2019-07-11T01:10:46 Z letrongdat Marriage questions (IZhO14_marriage) C++17
14 / 100
 8 ms 508 KB 
#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(auto v: E[u]) if (v <= ri) {
        if (!matched[v] || visit(matched[v])) {
            matched[v] = u;
            return true;
        } 
    }
    return false;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("a.inp", "r", stdin);
#endif // ONLINE_JUDGE
    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;
}

Compilation message

marriage.cpp: In function 'int main()':
marriage.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("a.inp", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 504 KB Output isn't correct
2 Incorrect 8 ms 504 KB Output isn't correct
3 Incorrect 4 ms 376 KB Output isn't correct
4 Incorrect 5 ms 376 KB Output isn't correct
5 Incorrect 4 ms 376 KB Output isn't correct
6 Incorrect 4 ms 504 KB Output isn't correct
7 Incorrect 4 ms 504 KB Output isn't correct
8 Incorrect 4 ms 504 KB Output isn't correct
9 Correct 4 ms 504 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Incorrect 4 ms 376 KB Output isn't correct
12 Correct 4 ms 504 KB Output is correct
13 Incorrect 4 ms 376 KB Output isn't correct
14 Incorrect 4 ms 504 KB Output isn't correct
15 Incorrect 4 ms 504 KB Output isn't correct
16 Incorrect 4 ms 376 KB Output isn't correct
17 Incorrect 4 ms 504 KB Output isn't correct
18 Incorrect 4 ms 504 KB Output isn't correct
19 Incorrect 4 ms 504 KB Output isn't correct
20 Incorrect 4 ms 376 KB Output isn't correct
21 Correct 4 ms 504 KB Output is correct
22 Incorrect 4 ms 376 KB Output isn't correct
23 Incorrect 4 ms 376 KB Output isn't correct
24 Incorrect 4 ms 376 KB Output isn't correct
25 Incorrect 4 ms 504 KB Output isn't correct
26 Incorrect 4 ms 376 KB Output isn't correct
27 Correct 4 ms 504 KB Output is correct
28 Incorrect 4 ms 504 KB Output isn't correct
29 Incorrect 4 ms 508 KB Output isn't correct
30 Incorrect 4 ms 376 KB Output isn't correct
31 Incorrect 4 ms 508 KB Output isn't correct
32 Incorrect 4 ms 504 KB Output isn't correct
33 Correct 4 ms 504 KB Output is correct
34 Incorrect 4 ms 376 KB Output isn't correct
35 Incorrect 4 ms 504 KB Output isn't correct
36 Incorrect 4 ms 504 KB Output isn't correct
37 Incorrect 4 ms 504 KB Output isn't correct
38 Incorrect 4 ms 376 KB Output isn't correct
39 Incorrect 4 ms 376 KB Output isn't correct
40 Correct 4 ms 376 KB Output is correct
41 Incorrect 4 ms 504 KB Output isn't correct
42 Incorrect 4 ms 376 KB Output isn't correct
43 Incorrect 4 ms 504 KB Output isn't correct
44 Incorrect 4 ms 504 KB Output isn't correct
45 Incorrect 4 ms 504 KB Output isn't correct
46 Incorrect 4 ms 504 KB Output isn't correct
47 Incorrect 4 ms 504 KB Output isn't correct
48 Incorrect 4 ms 504 KB Output isn't correct
49 Incorrect 4 ms 376 KB Output isn't correct
50 Incorrect 4 ms 504 KB Output isn't correct