oj.uz

답안 #171788

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171788 2019-12-30T12:05:06 Z VEGAnn 결혼 문제 (IZhO14_marriage) C++14
20 / 100
 1373 ms 968 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define pii pair<int, int>
#define pi3 pair<pii, int>
#define MP3(a,b,c) MP(MP(a, b), c)
using namespace std;
const int oo = 1e9;
const int N = 2000;
const int K = 110;
const int PW = 20;

struct edge{
    int x, y, cap, flow;

    edge(int _x, int _y, int _c, int _f): x(_x), y(_y), cap(_c), flow(_f) {}
};

vector<edge> edges;
queue<int> q;
vector<int> g[N];
int ans = 0, s, t, n, m, k, dst[N], ptr[N], X[N], Y[N];

void add_edge(int x, int y, int cap){

    g[x].PB(sz(edges));
    edges.PB(edge(x, y, cap, 0));

    g[y].PB(sz(edges));
    edges.PB(edge(y, x, 0, 0));

}

bool bad(int l, int r, int v){
    if (v == s || v == t || v < m) return 0;
    return !(m + l <= v && v <= m + r);
}

bool bfs(){
    fill(dst, dst + t + 1, oo);

    dst[s] = 0;
    while (sz(q)) q.pop();
    q.push(s);

    while (sz(q)){
        int v = q.front(); q.pop();

        for (int nm : g[v]){
            edge u = edges[nm];
            if (u.cap > u.flow && dst[u.y] > dst[v] + 1){
                dst[u.y] = dst[v] + 1;
                q.push(u.y);
            }
        }
    }

    return (dst[t] < oo);
}

int dfs(int v, int pshd){
    if (pshd == 0) return 0;
    if (v == t) return pshd;
    for (; ptr[v] < sz(g[v]); ptr[v]++){
        int nm = g[v][ptr[v]];
        edge u = edges[nm];
        if (dst[u.y] != dst[v] + 1) continue;
        int nw = dfs(u.y, min(pshd, u.cap - u.flow));
        if (nw){
            edges[nm].flow += nw;
            edges[nm ^ 1].flow -= nw;
            return nw;
        }
    }
    return 0;
}

bool ok(int l, int r){

    for (int i = 0; i <= t; i++)
        g[i].clear();

    edges.clear();

    for (int i = 0; i < k; i++){
        if (bad(l, r, X[i]) || bad(l, r, Y[i])) continue;
        add_edge(X[i], m + Y[i], 1);
    }

    for (int i = 0; i < m; i++)
        add_edge(s, i, 1);

    for (int i = l; i <= r; i++)
        add_edge(m + i, t, 1);

    int flow = 0;

    while (bfs()){
        fill(ptr, ptr + t + 1, 0);
        int pshd = dfs(s, oo);
        while (pshd > 0){
            flow += pshd;
            pshd = dfs(s, oo);
        }
    }

    return (flow == m);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m >> k;

    for (int i = 0; i < k; i++){
        cin >> Y[i] >> X[i];
        Y[i]--; X[i]--;
    }

    s = n + m;
    t = n + m + 1;

    for (int l = 0, r = 0; l < n; l++){
        while (r < n && !ok(l, r))
            r++;
        if (r >= n) break;
        ans += n - r;
    }

    cout << ans;

    return 0;
}

Subtask #1
20.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Incorrect 2 ms 376 KB Output isn't correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct
13 Incorrect 2 ms 376 KB Output isn't correct
14 Incorrect 3 ms 376 KB Output isn't correct
15 Incorrect 2 ms 504 KB Output isn't correct
16 Incorrect 3 ms 376 KB Output isn't correct
17 Incorrect 2 ms 376 KB Output isn't correct
18 Incorrect 2 ms 376 KB Output isn't correct
19 Incorrect 20 ms 632 KB Output isn't correct
20 Incorrect 10 ms 508 KB Output isn't correct
21 Correct 4 ms 376 KB Output is correct
22 Incorrect 3 ms 376 KB Output isn't correct
23 Incorrect 8 ms 504 KB Output isn't correct
24 Incorrect 7 ms 504 KB Output isn't correct
25 Incorrect 12 ms 632 KB Output isn't correct
26 Incorrect 157 ms 604 KB Output isn't correct
27 Correct 30 ms 632 KB Output is correct
28 Incorrect 18 ms 632 KB Output isn't correct
29 Incorrect 14 ms 504 KB Output isn't correct
30 Incorrect 11 ms 504 KB Output isn't correct
31 Incorrect 91 ms 728 KB Output isn't correct
32 Incorrect 1373 ms 968 KB Output isn't correct
33 Correct 182 ms 632 KB Output is correct
34 Incorrect 146 ms 692 KB Output isn't correct
35 Incorrect 67 ms 632 KB Output isn't correct
36 Incorrect 67 ms 720 KB Output isn't correct
37 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 3 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 4 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Runtime error 4 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
44 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
45 Runtime error 4 ms 892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
46 Runtime error 4 ms 860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Runtime error 4 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
48 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
49 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
50 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)