| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 95448 | 2019-02-01T08:42:30 Z | choikiwon | Marriage questions (IZhO14_marriage) | C++17 | 1500 ms | 263168 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN = 100010;
int N, M, K;
vector<int> adj[MN], U, V;
int matched[MN], chk[MN], who[MN], vis[MN];
bool dfs(int u, int t, int lb, int ub) {
if(t) {
if(!chk[u]) {
chk[u] = 1;
return true;
}
int e = who[u];
int v = U[e] + V[e] - u;
if(dfs(v, 0, lb, ub)) {
matched[e] = 0;
return true;
}
else return false;
}
else {
for(int i = 0; i < adj[u].size(); i++) {
int e = adj[u][i];
int v = U[e] + V[e] - u;
if(v < N && (v < lb || ub < v)) continue;
if(chk[v] && vis[v]) continue;
if(!matched[e] && dfs(v, 1, lb, ub)) {
who[u] = e;
who[v] = e;
matched[e] = 1;
return true;
}
}
return false;
}
}
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(i);
adj[b + N].push_back(i);
U.push_back(a);
V.push_back(b + N);
}
ll ans = 0;
int matching = 0;
int j = 0;
for(int i = 0; i < N; i++) {
while(j < N && matching < M) {
for(int k = 0; k < M; k++) vis[N + k] = 0;
if(dfs(j, 0, i, j)) {
matching++;
chk[j] = 1;
}
j++;
}
if(matching < M) break;
ans += N - j + 1;
if(chk[i]) {
matching--;
int v = U[ who[i] ] + V[ who[i] ] - i;
chk[v] = 0;
for(int k = 0; k < M; k++) if(chk[N + k]) {
int e = who[N + k];
int x = U[e] + V[e] - (N + k);
vis[x] = 0;
}
if(dfs(v, 0, i + 1, j - 1)) {
matching++;
chk[v] = 1;
}
}
}
printf("%lld", ans);
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 205 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 | Runtime error | 208 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 | Correct | 4 ms | 2680 KB | Output is correct |
| 4 | Correct | 3 ms | 2680 KB | Output is correct |
| 5 | Correct | 3 ms | 2680 KB | Output is correct |
| 6 | Correct | 4 ms | 2680 KB | Output is correct |
| 7 | Runtime error | 226 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 | Correct | 4 ms | 2680 KB | Output is correct |
| 9 | Correct | 4 ms | 2680 KB | Output is correct |
| 10 | Runtime error | 209 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 | Correct | 3 ms | 2680 KB | Output is correct |
| 12 | Correct | 3 ms | 2680 KB | Output is correct |
| 13 | Correct | 3 ms | 2680 KB | Output is correct |
| 14 | Runtime error | 196 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 15 | Runtime error | 210 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 | Correct | 3 ms | 2680 KB | Output is correct |
| 17 | Runtime error | 210 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 18 | Runtime error | 252 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 19 | Runtime error | 208 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 20 | Runtime error | 225 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 21 | Correct | 4 ms | 2680 KB | Output is correct |
| 22 | Correct | 4 ms | 2680 KB | Output is correct |
| 23 | Execution timed out | 1573 ms | 2680 KB | Time limit exceeded |
| 24 | Execution timed out | 1564 ms | 2680 KB | Time limit exceeded |
| 25 | Runtime error | 228 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 26 | Runtime error | 243 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 27 | Correct | 4 ms | 2680 KB | Output is correct |
| 28 | Correct | 4 ms | 2680 KB | Output is correct |
| 29 | Execution timed out | 1575 ms | 2988 KB | Time limit exceeded |
| 30 | Execution timed out | 1571 ms | 3064 KB | Time limit exceeded |
| 31 | Runtime error | 231 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 32 | Runtime error | 214 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 33 | Correct | 4 ms | 2808 KB | Output is correct |
| 34 | Correct | 6 ms | 2808 KB | Output is correct |
| 35 | Execution timed out | 1559 ms | 4584 KB | Time limit exceeded |
| 36 | Execution timed out | 1571 ms | 4328 KB | Time limit exceeded |
| 37 | Runtime error | 243 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 38 | Execution timed out | 1566 ms | 4840 KB | Time limit exceeded |
| 39 | Correct | 58 ms | 3064 KB | Output is correct |
| 40 | Runtime error | 215 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 41 | Execution timed out | 1582 ms | 103848 KB | Time limit exceeded |
| 42 | Execution timed out | 1565 ms | 3448 KB | Time limit exceeded |
| 43 | Execution timed out | 1577 ms | 3824 KB | Time limit exceeded |
| 44 | Execution timed out | 1576 ms | 4580 KB | Time limit exceeded |
| 45 | Runtime error | 340 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 46 | Runtime error | 301 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 47 | Execution timed out | 1554 ms | 4936 KB | Time limit exceeded |
| 48 | Execution timed out | 1558 ms | 4812 KB | Time limit exceeded |
| 49 | Runtime error | 284 ms | 263168 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 50 | Correct | 83 ms | 3064 KB | Output is correct |