oj.uz

Submission #345344

# Submission time Handle Problem Language Result Execution time Memory
345344 2021-01-07T07:47:46 Z vonatlus Marriage questions (IZhO14_marriage) C++17
34 / 100
 1500 ms 5268 KB 
/// wa 

#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:36777216")

#include<bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define sz(x) (int) x.size()
#define all(z) (z).begin(), (z).end()
 
using namespace std;

using ll = long long;
using pii = pair<int, int>;                                   

const int MOD = 1e9 + 7; 
const int INF = 1e9 + 1e2;
  
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void fin() {
#ifdef AM
    freopen(".in", "r", stdin);
#endif        
}                   

const bool flag = 0;

const int N = 1e5+10;

int was[N];

int mt[N], p[N], tmp;

vector<int> adj[N];
                     
bool dfs(int x) {
    if (was[x] == tmp) return 0;
    was[x] = tmp;
    for (int to : adj[x]) {
        if (mt[to] == -1) {
            mt[to] = x;
            p[x] = to;
            return 1;
        }
    }
    for (int to : adj[x]) {
        if (dfs(to)) {
            mt[to] = x;
            p[x] = to;
            return 1;
        }
    }
    return 0;
}

void ma1n() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> g(n);
    for (int u, v; k--;) {
        cin >> u >> v;
        u--, v--;
        g[u].pb(v);
    }
    int r = 0;
    ll ans = 0;
    memset(mt, -1, sizeof(mt));
    int prev = -1;
    for (int l = 0; l < n; ++l) {
        bool ok = 0;
        while (r < n && !ok) {
            for (int to : g[r]) {
                adj[to].pb(r);
            }
            fill(p, p+m, -1);
            for (int i = 0; i < m; ++i) {
                tmp++;
                dfs(i);
            }
            ok = 1;
            for (int i = 0; i < m; ++i) {
                if (~p[i]) {
                    mt[p[i]] = -1;
                } else {          
                    ok = 0;
                }
            }
            r++;
        }        
        for (int to : g[l]) {
            adj[to].erase(find(all(adj[to]), l));
        }
        if (ok) {
            ans += n-r+1;
        }
    }
    cout << ans;
} 

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr), fin();
    int ts = 1;
    if (flag) {
        cin >> ts;
    }
    while (ts--) {
        ma1n(); 
    }
    return 0;
}

Compilation message

marriage.cpp: In function 'void ma1n()':
marriage.cpp:72:9: warning: unused variable 'prev' [-Wunused-variable]
   72 |     int prev = -1;
      |         ^~~~

Subtask #1
34.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3052 KB Output isn't correct
2 Incorrect 3 ms 3052 KB Output isn't correct
3 Incorrect 3 ms 3052 KB Output isn't correct
4 Incorrect 3 ms 3052 KB Output isn't correct
5 Correct 3 ms 3052 KB Output is correct
6 Correct 3 ms 3052 KB Output is correct
7 Incorrect 3 ms 3052 KB Output isn't correct
8 Correct 3 ms 3052 KB Output is correct
9 Correct 3 ms 3052 KB Output is correct
10 Correct 2 ms 3052 KB Output is correct
11 Correct 3 ms 3052 KB Output is correct
12 Correct 2 ms 3052 KB Output is correct
13 Incorrect 2 ms 3052 KB Output isn't correct
14 Incorrect 3 ms 3052 KB Output isn't correct
15 Incorrect 2 ms 3052 KB Output isn't correct
16 Incorrect 2 ms 3052 KB Output isn't correct
17 Correct 3 ms 3052 KB Output is correct
18 Correct 3 ms 3052 KB Output is correct
19 Incorrect 12 ms 3312 KB Output isn't correct
20 Incorrect 7 ms 3052 KB Output isn't correct
21 Correct 3 ms 3052 KB Output is correct
22 Incorrect 3 ms 3052 KB Output isn't correct
23 Correct 3 ms 3052 KB Output is correct
24 Correct 3 ms 3052 KB Output is correct
25 Execution timed out 1585 ms 3312 KB Time limit exceeded
26 Incorrect 171 ms 3180 KB Output isn't correct
27 Correct 4 ms 3052 KB Output is correct
28 Incorrect 3 ms 3052 KB Output isn't correct
29 Incorrect 8 ms 3180 KB Output isn't correct
30 Incorrect 4 ms 3180 KB Output isn't correct
31 Execution timed out 1566 ms 3564 KB Time limit exceeded
32 Execution timed out 1576 ms 3244 KB Time limit exceeded
33 Correct 7 ms 3180 KB Output is correct
34 Incorrect 7 ms 3180 KB Output isn't correct
35 Correct 54 ms 4204 KB Output is correct
36 Correct 61 ms 4232 KB Output is correct
37 Execution timed out 1576 ms 3644 KB Time limit exceeded
38 Incorrect 50 ms 4608 KB Output isn't correct
39 Incorrect 129 ms 3456 KB Output isn't correct
40 Correct 970 ms 3692 KB Output is correct
41 Execution timed out 1575 ms 3720 KB Time limit exceeded
42 Incorrect 109 ms 4064 KB Output isn't correct
43 Incorrect 124 ms 4168 KB Output isn't correct
44 Incorrect 234 ms 4588 KB Output isn't correct
45 Execution timed out 1543 ms 4648 KB Time limit exceeded
46 Execution timed out 1553 ms 4900 KB Time limit exceeded
47 Incorrect 441 ms 5268 KB Output isn't correct
48 Incorrect 357 ms 5252 KB Output isn't correct
49 Execution timed out 1578 ms 4972 KB Time limit exceeded
50 Incorrect 427 ms 3948 KB Output isn't correct