# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
341231 | 2020-12-29T09:13:10 Z | juggernaut | Marriage questions (IZhO14_marriage) | C++14 | 1500 ms | 4204 KB |
#include<bits/stdc++.h> using namespace std; vector<int>g[100005]; int mt[100005]; int n,m,q; bool used[100001]; int X,Y; bool kuhn(int v){ if(used[v]||v<X||v>Y)return false; used[v]=true; for(int to:g[v]){ if(mt[to]==0||kuhn(mt[to])){ mt[to]=v; return true; } } return false; } bool check(int l,int r){ X=l,Y=r; for(int i=1;i<=n;i++)mt[i]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++)used[j]=false; kuhn(i); } int c=0; for(int i=1;i<=n;i++)if(mt[i])c++; return c==m; } int main(){ scanf("%d%d%d",&n,&m,&q); if(n<m||q<m)return puts("0"),0; while(q--){ int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); } int ans=0; for(int GL=1;GL<=n;GL++){ if(!check(GL,n))continue; int l=GL,r=n+1; while(l<r){ int mid=(l+r)>>1; if(check(GL,mid))r=mid; else l=mid+1; } ans+=n-l+1; } cout<<ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2668 KB | Output is correct |
2 | Correct | 2 ms | 2668 KB | Output is correct |
3 | Correct | 2 ms | 2668 KB | Output is correct |
4 | Correct | 2 ms | 2668 KB | Output is correct |
5 | Correct | 2 ms | 2668 KB | Output is correct |
6 | Correct | 2 ms | 2668 KB | Output is correct |
7 | Correct | 2 ms | 2796 KB | Output is correct |
8 | Correct | 2 ms | 2668 KB | Output is correct |
9 | Correct | 2 ms | 2668 KB | Output is correct |
10 | Correct | 2 ms | 2668 KB | Output is correct |
11 | Correct | 2 ms | 2668 KB | Output is correct |
12 | Correct | 2 ms | 2668 KB | Output is correct |
13 | Correct | 2 ms | 2668 KB | Output is correct |
14 | Correct | 2 ms | 2668 KB | Output is correct |
15 | Correct | 2 ms | 2668 KB | Output is correct |
16 | Correct | 2 ms | 2668 KB | Output is correct |
17 | Correct | 2 ms | 2668 KB | Output is correct |
18 | Correct | 2 ms | 2668 KB | Output is correct |
19 | Correct | 16 ms | 2668 KB | Output is correct |
20 | Correct | 10 ms | 2668 KB | Output is correct |
21 | Correct | 3 ms | 2668 KB | Output is correct |
22 | Correct | 7 ms | 2668 KB | Output is correct |
23 | Correct | 13 ms | 2668 KB | Output is correct |
24 | Correct | 9 ms | 2668 KB | Output is correct |
25 | Execution timed out | 1576 ms | 2796 KB | Time limit exceeded |
26 | Correct | 937 ms | 2796 KB | Output is correct |
27 | Correct | 71 ms | 2668 KB | Output is correct |
28 | Correct | 402 ms | 2668 KB | Output is correct |
29 | Execution timed out | 1583 ms | 2668 KB | Time limit exceeded |
30 | Execution timed out | 1528 ms | 2796 KB | Time limit exceeded |
31 | Execution timed out | 1590 ms | 3052 KB | Time limit exceeded |
32 | Execution timed out | 1544 ms | 2668 KB | Time limit exceeded |
33 | Correct | 519 ms | 2796 KB | Output is correct |
34 | Execution timed out | 1582 ms | 2668 KB | Time limit exceeded |
35 | Execution timed out | 1586 ms | 3180 KB | Time limit exceeded |
36 | Execution timed out | 1577 ms | 3180 KB | Time limit exceeded |
37 | Execution timed out | 1589 ms | 3180 KB | Time limit exceeded |
38 | Execution timed out | 1584 ms | 3436 KB | Time limit exceeded |
39 | Execution timed out | 1586 ms | 2924 KB | Time limit exceeded |
40 | Execution timed out | 1578 ms | 2924 KB | Time limit exceeded |
41 | Execution timed out | 1585 ms | 3052 KB | Time limit exceeded |
42 | Execution timed out | 1534 ms | 3180 KB | Time limit exceeded |
43 | Execution timed out | 1588 ms | 3180 KB | Time limit exceeded |
44 | Execution timed out | 1585 ms | 3308 KB | Time limit exceeded |
45 | Execution timed out | 1586 ms | 3436 KB | Time limit exceeded |
46 | Execution timed out | 1586 ms | 3820 KB | Time limit exceeded |
47 | Execution timed out | 1540 ms | 3948 KB | Time limit exceeded |
48 | Execution timed out | 1534 ms | 4204 KB | Time limit exceeded |
49 | Execution timed out | 1581 ms | 4076 KB | Time limit exceeded |
50 | Execution timed out | 1563 ms | 2924 KB | Time limit exceeded |