| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 306406 |
2020-09-25T12:44:58 Z |
colazcy |
Cipele (COCI18_cipele) |
C++17 |
|
1000 ms |
44280 KB |
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 1e5 + 100;
inline int read(){
int x = 0;char c = getchar();
while(!isdigit(c))c = getchar();
while(isdigit(c))x = x * 10 + c - '0',c = getchar();
return x;
}
int n,m,vl[maxn],vr[maxn];
namespace dinic{
const int INF = 0x7fffffff;
const int max = 5e3,maxm = 1e6;
struct Edge{
int from,to,cap,flow;
Edge() = default;
Edge(int a,int b,int c,int d):from(a),to(b),cap(c),flow(d){}
}Edges[maxm];
int head[maxn],nxt[maxm],tot = 1;
inline void clear(){
memset(head,0,sizeof(head));
memset(nxt,0,sizeof(nxt));
tot = 1;
}
inline void addedge(int from,int to,int cap){
Edges[++tot] = Edge(from,to,cap,0);
nxt[tot] = head[from];
head[from] = tot;
Edges[++tot] = Edge(to,from,0,0);
nxt[tot] = head[to];
head[to] = tot;
}
int d[maxn];
inline bool bfs(int s,int t){
queue<int> Q;
memset(d,-1,sizeof(d));
d[s] = 0;
Q.push(s);
while(!Q.empty()){
int u = Q.front();Q.pop();
for(int i = head[u];i;i = nxt[i]){
Edge &e = Edges[i];
if(e.cap > e.flow && d[e.to] == -1){
d[e.to] = d[u] + 1;
Q.push(e.to);
}
}
}
return d[t] != -1;
}
int cur[maxn];
inline int dfs(int u,int a,int t){
if(u == t || a == 0)return a;
int ret = 0,f;
for(int &i = cur[u];i;i = nxt[i]){
Edge &e = Edges[i];
if(d[u] + 1 == d[e.to] && (f = dfs(e.to,min(a,e.cap - e.flow),t)) > 0){
ret += f;
Edges[i].flow += f;
Edges[i ^ 1].flow -= f;
a -= f;
if(a == 0)break;
}
}
return ret;
}
inline int maxflow(int s,int t){
int ret = 0;
while(bfs(s,t)){
memcpy(cur,head,sizeof(head));
ret += dfs(s,INF,t);
}
return ret;
}
}
//namespace dinic{
// const int maxn = 5e3 + 100,maxm = 1e6;
// struct edge{int to,cap;}edges[maxm];
// int head[maxn],nxt[maxm],tot = 1;
// inline void clear(){
// memset(head,0,sizeof(head));
// memset(nxt,0,sizeof(nxt));
// tot = 1;
// }
// inline void addedge(int u,int v,int cap){
// edges[++tot] = edge{v,cap};
// nxt[tot] = head[u];
// head[u] = tot;
// edges[++tot] = edge{u,0};
// nxt[tot] = head[v];
// head[v] = tot;
// }
// int d[maxn];
// inline bool bfs(int s,int t){
// queue<int> q;
// memset(d,-1,sizeof(d));
// q.push(s);d[s] = 1;
// while(!q.empty()){
// int u = q.front();q.pop();
// for(int i = head[u];i;i = nxt[i]){
// const edge &e = edges[i];
// if(e.cap && d[e.to] == -1){
// d[e.to] = d[u] + 1;
// q.push(e.to);
// }
// }
// }
// return d[t] != -1;
// }
// int cur[maxn];
// inline int dfs(int u,int a,int t){
// if(u == t || !a)return a;
// int res = 0,f;
// for(int &i = cur[u];i;i = nxt[i]){
// edge &e = edges[i];
// if((d[u] + 1 == d[e.to]) && (f = dfs(e.to,min(e.cap,a),t))){
// edges[i].cap -= f;
// edges[i ^ 1].cap += f;
// a -= f;
// res += f;
// if(!a)break;
// }
// }
// return res;
// }
// inline int maxflow(int s,int t){
// int res = 0;
// while(bfs(s,t)){
// memcpy(cur,head,sizeof(head));
// res += dfs(s,0x7fffffff,t);
// }
// return res;
// }
//}
inline bool check(int limit){
int ss = n + m + 1,tt = ss + 1;
dinic::clear();
for(int i = 1;i <= n;i++){
int pos = lower_bound(vr + 1,vr + 1 + m,vl[i]) - vr;
if(pos == m + 1)pos = m;
for(int k = pos - 1;k >= 1 && abs(vl[i] - vr[k]) <= limit;k--)dinic::addedge(i,n + k,1);
for(int k = pos;k <= m && abs(vl[i] - vr[k]) <= limit;k++)dinic::addedge(i,n + k,1);
}
for(int i = 1;i <= n;i++)dinic::addedge(ss,i,1);
for(int i = 1;i <= m;i++)dinic::addedge(n + i,tt,1);
return dinic::maxflow(ss,tt) == min(n,m);
}
int main(){
// freopen("cipele.in","r",stdin);
// freopen("cipele.out","w",stdout);
n = read(),m = read();
for(int i = 1;i <= n;i++)vl[i] = read();
for(int i = 1;i <= m;i++)vr[i] = read();
sort(vl + 1,vl + 1 + n);
sort(vr + 1,vr + 1 + m);
int l = 0,r = max(abs(vl[1] - vr[m]),abs(vl[n] - vr[1])),ans = -1;
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid))ans = mid,r = mid - 1;
else l = mid + 1;
}
printf("%d\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
71 ms |
43896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
82 ms |
44280 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1079 ms |
20864 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
17280 KB |
Output is correct |
| 2 |
Runtime error |
47 ms |
43384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
46 ms |
42492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
46 ms |
42488 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
44 ms |
42472 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
75 ms |
43900 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
78 ms |
44152 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
75 ms |
44024 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
