Queshi group (school competition dichotomous chart + dichotomous)

subject

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/4532.html

meaning of the title

Let's divide n points into two groups to min imize max

thinking

Coloring contraction points of bipartite graphs divide contradictory points into two line segments

Find the maximum and minimum of all points. If it is the same line segment difference, it is the answer

Otherwise, these two points or line segments are divided into two groups of binary answers. Verify that for each group of contradictory line segments, discuss and divide them into two groups

Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
struct node
{
    int l,r;
}b[100005];
struct edge
{
    int v,nxt;
}e[200005];
int head[100005];
int vis[100006];
int a[100005];
int top;
int p,f;
int n;
int MAX,MIN;

void add(int u,int v)
{
    e[top].v = v;
    e[top].nxt = head[u];
    head[u] = top++;
}

void dfs(int u,int op)
{
    vis[u] = p + op;
    b[p+op].l = min(b[p+op].l,a[u]);
    b[p+op].r = max(b[p+op].r,a[u]);
    for(int i = head[u];i != -1;i = e[i].nxt)
    {
        int v = e[i].v;
        if(vis[v] == vis[u])
        {
            f = 1;
            return ;
        }
        if(vis[v] == 0)
        {
            if(op==0) dfs(v,1);
            else dfs(v,0);
        }
    }
}
int ok(int x)
{
    for(int i = 1;i <= n;i++)
    {
        if(vis[i] == 0&&a[i] > MIN + x&&a[i] < MAX - x)
        {
            return 0;
        }
    }
    for(int i = 1;i <= p;i+=2)
    {
        if((b[i].r>MIN+x||b[i+1].l<MAX-x)&&(b[i+1].r>MIN+x||b[i].l<MAX-x))
            return 0;
    }
    return 1;
}
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&a[i]);
    }
    int m;
    scanf("%d",&m);
    memset(head,-1,sizeof(head));
    top = 0;
    for(int i = 1;i <= m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    memset(vis,0,sizeof(vis));
    p = 1;
    f = 0;
    for(int i = 1;i <= n;i++)
    {
        if(head[i] == -1) continue;
        else if(vis[i] == 0)
        {
            b[p].l = b[p+1].l = 100000000 + 10;
            b[p].r = b[p+1].r = -1;
            dfs(i,0);
            p+=2;
            if(f)
            {
                printf("impossible\n");
                return 0;
            }
        }
    }
    p--;
    MAX = -1,MIN = 100000000 + 10;
    for(int i = 1;i <= p;i++)
    {
        MIN = min(MIN,b[i].l);
        MAX = max(MAX,b[i].r);
    }
    for(int i = 1;i <= n;i++)
    {
        if(vis[i] == 0)
        {
            MIN = min(MIN,a[i]);
            MAX = max(MAX,a[i]);
        }
    }
    for(int i = 1;i <= p;i++)
    {
        if(b[i].l==MIN&&b[i].r == MAX)
        {
            printf("%d\n",MAX-MIN);
            return 0;
        }
    }
    int l = 0,r = MAX - MIN;
    while(l+1<r)
    {
        int mid = (l + r)>>1;
        if(ok(mid))
        {
            r = mid;
        }
        else l = mid;
    }
    if(ok(l)) printf("%d\n",l);
    else printf("%d\n",r);
    return 0;
}

 

Tags: Programming PHP

Posted on Sat, 02 Nov 2019 19:55:46 -0700 by trauch