oj.uz

답안 #345334

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
345334 2021-01-07T07:39:48 Z vonatlus 결혼 문제 (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));
    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 += (l-prev) * 1ll * (n-r+1);
            prev = l;
        }
    }
    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

# 결과 실행 시간 메모리 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 504 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 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 524 KB Output is correct
19 Incorrect 11 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 1586 ms 800 KB Time limit exceeded
26 Incorrect 166 ms 620 KB Output isn't correct
27 Correct 1 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 640 KB Output isn't correct
31 Execution timed out 1572 ms 940 KB Time limit exceeded
32 Execution timed out 1588 ms 748 KB Time limit exceeded
33 Correct 5 ms 620 KB Output is correct
34 Incorrect 5 ms 624 KB Output isn't correct
35 Correct 49 ms 1644 KB Output is correct
36 Correct 60 ms 1516 KB Output is correct
37 Execution timed out 1572 ms 1080 KB Time limit exceeded
38 Incorrect 45 ms 1900 KB Output isn't correct
39 Runtime error 54 ms 1644 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 67 ms 1772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Execution timed out 1598 ms 1280 KB Time limit exceeded
42 Incorrect 112 ms 1388 KB Output isn't correct
43 Incorrect 106 ms 1540 KB Output isn't correct
44 Incorrect 186 ms 2028 KB Output isn't correct
45 Runtime error 70 ms 3564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Execution timed out 1584 ms 2324 KB Time limit exceeded
47 Incorrect 430 ms 2668 KB Output isn't correct
48 Incorrect 418 ms 2668 KB Output isn't correct
49 Execution timed out 1522 ms 2404 KB Time limit exceeded
50 Runtime error 111 ms 2412 KB Execution killed with signal 11 (could be triggered by violating memory limits)