Submission #306406

#	Time	Username	Problem	Language	Result	Execution time	Memory
306406		colazcy	Cipele (COCI18_cipele)	C++17	0 / 90	1079 ms	44280 KiB

cipele

#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;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9