oj.uz

Submission #345386

# Submission time Handle Problem Language Result Execution time Memory
345386 2021-01-07T08:21:47 Z vonatlus Marriage questions (IZhO14_marriage) C++17
44 / 100
 1500 ms 17072 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 = 3e5+10;
 
int was[N];
 
int mt[N], p[N], tmp;
 
vector<int> adj[N], g[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(mt[to])) {
            mt[to] = x;
            p[x] = to;
            return 1;
        }
    }
    return 0;
}
 
void ma1n() {
    int n, m, k;
    cin >> n >> m >> k;
    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:71:9: warning: unused variable 'prev' [-Wunused-variable]
   71 |     int prev = -1;
      |         ^~~~

Subtask #1
44.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 15596 KB Output isn't correct
2 Incorrect 10 ms 15596 KB Output isn't correct
3 Incorrect 13 ms 15596 KB Output isn't correct
4 Incorrect 12 ms 15596 KB Output isn't correct
5 Correct 14 ms 15596 KB Output is correct
6 Correct 11 ms 15596 KB Output is correct
7 Correct 11 ms 15596 KB Output is correct
8 Correct 12 ms 15596 KB Output is correct
9 Correct 11 ms 15596 KB Output is correct
10 Correct 13 ms 15596 KB Output is correct
11 Correct 11 ms 15596 KB Output is correct
12 Correct 12 ms 15596 KB Output is correct
13 Incorrect 12 ms 15596 KB Output isn't correct
14 Correct 13 ms 15596 KB Output is correct
15 Incorrect 12 ms 15596 KB Output isn't correct
16 Incorrect 11 ms 15596 KB Output isn't correct
17 Correct 12 ms 15596 KB Output is correct
18 Correct 11 ms 15596 KB Output is correct
19 Correct 16 ms 15596 KB Output is correct
20 Correct 12 ms 15596 KB Output is correct
21 Correct 10 ms 15568 KB Output is correct
22 Incorrect 13 ms 15596 KB Output isn't correct
23 Correct 11 ms 15596 KB Output is correct
24 Correct 12 ms 15596 KB Output is correct
25 Correct 38 ms 15748 KB Output is correct
26 Incorrect 15 ms 15596 KB Output isn't correct
27 Correct 11 ms 15596 KB Output is correct
28 Incorrect 14 ms 15596 KB Output isn't correct
29 Incorrect 16 ms 15724 KB Output isn't correct
30 Incorrect 14 ms 15724 KB Output isn't correct
31 Execution timed out 1559 ms 16108 KB Time limit exceeded
32 Incorrect 346 ms 15732 KB Output isn't correct
33 Correct 16 ms 15596 KB Output is correct
34 Incorrect 24 ms 15724 KB Output isn't correct
35 Correct 81 ms 16624 KB Output is correct
36 Correct 74 ms 16620 KB Output is correct
37 Execution timed out 1543 ms 16192 KB Time limit exceeded
38 Incorrect 59 ms 16968 KB Output isn't correct
39 Incorrect 318 ms 15852 KB Output isn't correct
40 Correct 306 ms 15952 KB Output is correct
41 Incorrect 427 ms 16260 KB Output isn't correct
42 Incorrect 125 ms 16172 KB Output isn't correct
43 Incorrect 109 ms 16364 KB Output isn't correct
44 Incorrect 229 ms 16876 KB Output isn't correct
45 Incorrect 852 ms 16448 KB Output isn't correct
46 Execution timed out 1584 ms 16864 KB Time limit exceeded
47 Incorrect 391 ms 17072 KB Output isn't correct
48 Incorrect 425 ms 17004 KB Output isn't correct
49 Execution timed out 1573 ms 16748 KB Time limit exceeded
50 Incorrect 854 ms 15964 KB Output isn't correct