oj.uz

Submission #345330

# Submission time Handle Problem Language Result Execution time Memory
345330 2021-01-07T07:35:24 Z vonatlus Marriage questions (IZhO14_marriage) C++14
32 / 100
 1500 ms 3564 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;

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));
    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;
}

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 492 KB Output isn't correct
3 Incorrect 1 ms 492 KB Output isn't correct
4 Incorrect 1 ms 640 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 1 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 492 KB Output is correct
19 Incorrect 9 ms 492 KB Output isn't correct
20 Incorrect 5 ms 492 KB Output isn't correct
21 Correct 1 ms 492 KB Output is correct
22 Incorrect 1 ms 492 KB Output isn't correct
23 Correct 1 ms 492 KB Output is correct
24 Correct 1 ms 492 KB Output is correct
25 Execution timed out 1570 ms 864 KB Time limit exceeded
26 Incorrect 176 ms 636 KB Output isn't correct
27 Correct 2 ms 492 KB Output is correct
28 Incorrect 1 ms 492 KB Output isn't correct
29 Incorrect 3 ms 620 KB Output isn't correct
30 Incorrect 3 ms 620 KB Output isn't correct
31 Execution timed out 1534 ms 1088 KB Time limit exceeded
32 Execution timed out 1557 ms 676 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 57 ms 1644 KB Output is correct
36 Correct 52 ms 1516 KB Output is correct
37 Execution timed out 1528 ms 1132 KB Time limit exceeded
38 Incorrect 47 ms 1848 KB Output isn't correct
39 Runtime error 62 ms 1644 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 65 ms 1772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Execution timed out 1570 ms 1148 KB Time limit exceeded
42 Incorrect 110 ms 1484 KB Output isn't correct
43 Incorrect 125 ms 1516 KB Output isn't correct
44 Incorrect 243 ms 2028 KB Output isn't correct
45 Runtime error 78 ms 3564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Execution timed out 1545 ms 2324 KB Time limit exceeded
47 Incorrect 404 ms 2656 KB Output isn't correct
48 Incorrect 452 ms 2668 KB Output isn't correct
49 Execution timed out 1548 ms 2400 KB Time limit exceeded
50 Runtime error 142 ms 2504 KB Execution killed with signal 11 (could be triggered by violating memory limits)