답안 #95458 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95458	2019-02-01T10:33:32 Z	choikiwon	결혼 문제 (IZhO14_marriage)	C++17	42 / 100	122 ms	8152 KB

marriage

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MN = 100010;

int V, E, src, snk;
vector<int> la, nxt, oppo, capa;
void init() {
    E = 0;
    la.clear(); nxt.clear(); oppo.clear(); capa.clear();
    la = vector<int>(V, -1);
}
void add(int u, int v, int c) {
    nxt.push_back(la[u]);
    la[u] = E++;
    oppo.push_back(v);
    capa.push_back(c);
}
vector<int> dist;
queue<int> q;
bool bfs() {
    dist = vector<int>(V, -1);
    q.push(src);
    dist[src] = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop();

        for(int i = la[u]; i != -1; i = nxt[i]) {
            int v = oppo[i];
            if(capa[i] && dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist[snk] != -1;
}
vector<int> laa;
int dfs(int u, int f) {
    if(u == snk) return f;
    for(int i = laa[u]; i != -1; i = nxt[i]) {
        laa[u] = i;
        int v = oppo[i];
        if(capa[i] && dist[v] == dist[u] + 1) {
            if(int tmp = dfs(v, min(f, capa[i]))) {
                capa[i] -= tmp;
                capa[i ^ 1] += tmp;
                return tmp;
            }
        }
    }
    return 0;
}
int dinic() {
    int tf = 0;
    while(bfs()) {
        laa = la;
        while(int tmp = dfs(src, 1e9)) tf += tmp;
    }
    return tf;
}

int N, M, K;
vector<int> adj[MN];
int who[MN];

void con(int x) {
    V = N + M + 2, src = V - 2, snk = V - 1;
    init();
    for(int i = 0; i <= x; i++) {
        add(src, i, 1);
        add(i, src, 0);
    }
    for(int i = 0; i < M; i++) {
        add(N + i, snk, 1);
        add(snk, N + i, 0);
    }
    for(int u = 0; u <= x; u++) {
        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];

            add(u, v, 1);
            add(v, u, 0);
        }
    }
}

int main() {
    scanf("%d %d %d", &N, &M, &K);

    for(int i = 0; i < K; i++) {
        int a, b; scanf("%d %d", &a, &b);
        a--; b--;

        adj[a].push_back(N + b);
        adj[N + b].push_back(a);
    }
    for(int i = 0; i < M; i++) {
        sort(adj[N + i].begin(), adj[N + i].end());
        reverse(adj[N + i].begin(), adj[N + i].end());
    }

    int s = 0, e = N - 1, p = -1;
    while(s <= e) {
        int m = (s + e)>>1;

        con(m);
        if(dinic() == M) {
            p = m;
            e = m - 1;
        }
        else s = m + 1;
    }

    con(p);
    dinic();

    memset(who, -1, sizeof(who));
    for(int u = 0; u <= p; u++) {
        for(int i = la[u]; i != -1; i = nxt[i]) {
            int v = oppo[i];
            if(v != src && !capa[i]) {
                who[u] = v;
                who[v] = u;
                break;
            }
        }
    }

    ll ans = N - p;
    for(int i = 1; i < N; i++) {
        if(who[i - 1] != -1) {
            int v = who[i - 1];
            while(adj[v].size() && (who[ adj[v].back() ] != -1 || adj[v].back() < i)) {
                adj[v].pop_back();
            }
            if(adj[v].size()) {
                p = max(p, adj[v].back());
                who[ adj[v].back() ] = v;
                who[v] = adj[v].back();
            }
            else break;
        }
        ans += N - p;
    }
    printf("%lld", ans);
}

Compilation message

marriage.cpp: In function 'void con(int)':
marriage.cpp:81:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < adj[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~
marriage.cpp: In function 'int main()':
marriage.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &M, &K);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:94:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d %d", &a, &b);
                   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
42.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	3064 KB	Output isn't correct
2	Incorrect	4 ms	3064 KB	Output isn't correct
3	Correct	4 ms	3064 KB	Output is correct
4	Correct	4 ms	3064 KB	Output is correct
5	Correct	3 ms	3064 KB	Output is correct
6	Correct	4 ms	3064 KB	Output is correct
7	Incorrect	3 ms	3064 KB	Output isn't correct
8	Correct	3 ms	3064 KB	Output is correct
9	Incorrect	4 ms	3064 KB	Output isn't correct
10	Incorrect	4 ms	3192 KB	Output isn't correct
11	Correct	3 ms	3064 KB	Output is correct
12	Incorrect	4 ms	3064 KB	Output isn't correct
13	Correct	4 ms	3064 KB	Output is correct
14	Incorrect	4 ms	3064 KB	Output isn't correct
15	Incorrect	4 ms	3064 KB	Output isn't correct
16	Correct	4 ms	3064 KB	Output is correct
17	Incorrect	4 ms	3064 KB	Output isn't correct
18	Incorrect	4 ms	3064 KB	Output isn't correct
19	Incorrect	5 ms	3192 KB	Output isn't correct
20	Incorrect	4 ms	3064 KB	Output isn't correct
21	Incorrect	4 ms	3064 KB	Output isn't correct
22	Correct	4 ms	3064 KB	Output is correct
23	Incorrect	4 ms	3064 KB	Output isn't correct
24	Incorrect	4 ms	3064 KB	Output isn't correct
25	Incorrect	9 ms	3448 KB	Output isn't correct
26	Incorrect	5 ms	3192 KB	Output isn't correct
27	Incorrect	5 ms	3064 KB	Output isn't correct
28	Correct	4 ms	3064 KB	Output is correct
29	Correct	9 ms	3576 KB	Output is correct
30	Correct	8 ms	3576 KB	Output is correct
31	Incorrect	35 ms	4464 KB	Output isn't correct
32	Incorrect	11 ms	3448 KB	Output isn't correct
33	Incorrect	5 ms	3192 KB	Output isn't correct
34	Correct	5 ms	3192 KB	Output is correct
35	Incorrect	49 ms	6356 KB	Output isn't correct
36	Incorrect	41 ms	5984 KB	Output isn't correct
37	Incorrect	49 ms	4720 KB	Output isn't correct
38	Correct	72 ms	6996 KB	Output is correct
39	Correct	11 ms	3704 KB	Output is correct
40	Incorrect	42 ms	4140 KB	Output isn't correct
41	Incorrect	45 ms	4464 KB	Output isn't correct
42	Correct	35 ms	5092 KB	Output is correct
43	Correct	51 ms	5652 KB	Output is correct
44	Correct	81 ms	6992 KB	Output is correct
45	Incorrect	80 ms	5736 KB	Output isn't correct
46	Incorrect	103 ms	6756 KB	Output isn't correct
47	Correct	122 ms	8152 KB	Output is correct
48	Correct	96 ms	7888 KB	Output is correct
49	Incorrect	121 ms	6912 KB	Output isn't correct
50	Correct	21 ms	4468 KB	Output is correct

답안 #95458

Compilation message

Subtask #1 42.0 / 100.0

Subtask #1
42.0 / 100.0