oj.uz

Submission #345329

# Submission time Handle Problem Language Result Execution time Memory
345329 2021-01-07T07:32:38 Z vonatlus Marriage questions (IZhO14_marriage) C++14
32 / 100
 1500 ms 6888 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 = 2e3+10;
const int M = 3e4+10;

int was[N];

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

set<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));
    for (int l = 0; l < n; ++l) {
        bool ok = 0;
        while (r < n && !ok) {
            for (int to : g[r]) {
                adj[to].insert(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(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;
}

Subtask #1
32.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Incorrect 1 ms 620 KB Output isn't correct
3 Incorrect 1 ms 492 KB Output isn't correct
4 Incorrect 1 ms 492 KB Output isn't correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Incorrect 1 ms 492 KB Output isn't correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Incorrect 1 ms 492 KB Output isn't correct
14 Incorrect 1 ms 492 KB Output isn't correct
15 Incorrect 2 ms 492 KB Output isn't correct
16 Incorrect 1 ms 492 KB Output isn't correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Incorrect 24 ms 620 KB Output isn't correct
20 Incorrect 9 ms 620 KB Output isn't correct
21 Correct 2 ms 620 KB Output is correct
22 Incorrect 1 ms 620 KB Output isn't correct
23 Correct 2 ms 620 KB Output is correct
24 Correct 1 ms 620 KB Output is correct
25 Execution timed out 1573 ms 1008 KB Time limit exceeded
26 Incorrect 399 ms 748 KB Output isn't correct
27 Correct 2 ms 620 KB Output is correct
28 Incorrect 1 ms 620 KB Output isn't correct
29 Incorrect 5 ms 1004 KB Output isn't correct
30 Incorrect 4 ms 1004 KB Output isn't correct
31 Execution timed out 1568 ms 1416 KB Time limit exceeded
32 Execution timed out 1549 ms 900 KB Time limit exceeded
33 Correct 5 ms 620 KB Output is correct
34 Incorrect 5 ms 620 KB Output isn't correct
35 Correct 426 ms 5368 KB Output is correct
36 Correct 399 ms 4736 KB Output is correct
37 Execution timed out 1546 ms 1228 KB Time limit exceeded
38 Incorrect 120 ms 5976 KB Output isn't correct
39 Runtime error 32 ms 1516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 89 ms 2036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Execution timed out 1539 ms 1356 KB Time limit exceeded
42 Incorrect 126 ms 2796 KB Output isn't correct
43 Incorrect 151 ms 3692 KB Output isn't correct
44 Incorrect 320 ms 5780 KB Output isn't correct
45 Runtime error 86 ms 3820 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Execution timed out 1556 ms 2624 KB Time limit exceeded
47 Incorrect 458 ms 6888 KB Output isn't correct
48 Incorrect 458 ms 6380 KB Output isn't correct
49 Execution timed out 1569 ms 2668 KB Time limit exceeded
50 Runtime error 108 ms 2540 KB Execution killed with signal 11 (could be triggered by violating memory limits)