#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);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
