CF538H. Summer Dichotomy
题目大意
题解
看CF上标签的意思应该是2-sat+数据结构优化建图难怪是H题
看了题解,其实想想(也许)能够想出来
设两组的最大l和最小r为l1r1l2r2,则满足l1+l2<=t2且r1+r2>=t1
根据max(l)和min(r)是否在同一区间分类讨论
判断很简单,设代表1和2区间的点,两点之间有边即不能在同一区间
然后判是否是二分图,以及新建的点颜色是否不同即可
最后具体分的人数要考虑一下,还要特判一下全在某个集合的和max(l)>t2的
大概是这样,有一点细节
code
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define inf 2133333333
#define ll long long
//#define file
using namespace std;
int a[600001][2],ls[100003],L[100001],R[100001],b[100001][2],f[100003],len,t1,t2,n,m,i,j,k,l,ml,mr,l1,r1,l2,r2;
bool bz;
void New(int x,int y) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;}
void NEW(int x,int y) {New(x,y);New(y,x);}
void dfs(int t)
{
int i;
if (!bz) return;
for (i=ls[t]; i; i=a[i][1])
if (!f[a[i][0]])
{f[a[i][0]]=3-f[t];dfs(a[i][0]);}
else
if (f[a[i][0]]==f[t]) {bz=0;return;}
}
void work(bool tp)
{
int i,j,k,l;
memset(ls,0,sizeof(ls));len=0;
memset(f,0,sizeof(f));
fo(i,1,m) NEW(b[i][0],b[i][1]);
fo(i,1,n)
if (!tp)
{
if (R[i]<t1-mr || R[i]<ml) NEW(n+1,i);
if (L[i]>t2-ml || mr<L[i]) NEW(n+2,i);
}
else
if (!(L[i]<=t2-ml && R[i]>=t1-mr)) NEW(n+2,i);
bz=1;
f[n+1]=1;dfs(n+1);
if (f[n+2]==1 || !bz) return;
f[n+2]=2;dfs(n+2);
if (bz)
{
fo(i,1,n)
if (!f[i])
{
f[i]=1;dfs(i);
if (!bz) return;
}
}
if (bz)
{
printf("POSSIBLE\n");
l1=l2=-inf,r1=r2=inf;
if (!tp) l1=ml,r2=mr; else l1=ml,r1=mr;
fo(i,1,n)
if (f[i]==1)
l1=max(l1,L[i]),r1=min(r1,R[i]);
else
l2=max(l2,L[i]),r2=min(r2,R[i]);
fo(i,1,n) if (f[i]==2) break;
if (i>n)
{printf("%d %d\n",l1,max(t1-l1,0));}
else
{k=max(l1+l2,t1);printf("%d %d\n",l1+max((k-l1)-r2,0),k-(l1+max((k-l1)-r2,0)));}
fo(i,1,n) printf("%d",f[i]);
printf("\n");
exit(0);
}
}
int main()
{
#ifdef file
freopen("CF538H.in","r",stdin);
#endif
scanf("%d%d",&t1,&t2);
scanf("%d%d",&n,&m);
ml=-inf;mr=inf;
fo(i,1,n) scanf("%d%d",&L[i],&R[i]),ml=max(ml,L[i]),mr=min(mr,R[i]);
fo(i,1,m) scanf("%d%d",&b[i][0],&b[i][1]);
if (ml>t2) {printf("IMPOSSIBLE\n");return 0;}
if (n==1)
{
if (L[1]<=t2 && t1<=R[1]) {printf("POSSIBLE\n");printf("%d %d\n",max(L[1],t1),0);printf("1\n");}
else printf("IMPOSSIBLE\n");
return 0;
}
if (ml>mr) {fo(i,1,n) if (mr<L[i] && R[i]<ml) {printf("IMPOSSIBLE\n");return 0;}}
work(0);
if (ml<=mr)
work(1);
printf("IMPOSSIBLE\n");
fclose(stdin);
fclose(stdout);
return 0;
}