1001 Monitor the Alpacas
两边离散化。暴力扫C就过了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 1000010
bool vis1[maxn],vis2[maxn];
int Hash[maxn],h[][maxn];
int tt[],num[],c1[maxn],c2[maxn];
int sz[][maxn]; struct node
{
int to,pre;
} edge[][maxn]; void add(int op,int from,int to)
{
tt[op]++;
edge[op][tt[op]].pre=h[op][from];
edge[op][tt[op]].to=to;
h[op][from]=tt[op];
} int id(int op,int x)
{
return lower_bound(Hash,Hash+num[op],x)-Hash;
} int main(void)
{
int T; cin>>T;
for(int kase=;kase<=T;kase++)
{
memset(tt,,sizeof(tt));
memset(h,,sizeof(h));
memset(sz,,sizeof(sz));
memset(Hash,,sizeof(Hash));
int n; scanf("%d",&n);
for(int i=;i<n;i++) scanf("%d%d",c1+i,c2+i);
for(int i=;i<n;i++) Hash[i]=c1[i];
sort(Hash,Hash+n);
num[]=unique(Hash,Hash+n)-Hash;
for(int i=;i<n;i++)
{
add(,c1[i]=id(,c1[i]),i);
sz[][c1[i]]++;
}
for(int i=;i<n;i++) Hash[i]=c2[i];
sort(Hash,Hash+n);
num[]=unique(Hash,Hash+n)-Hash;
for(int i=;i<n;i++)
{
add(,c2[i]=id(,c2[i]),i);
sz[][c2[i]]++;
}
int S=,M=,O=;
memset(vis1,,sizeof(vis1));
memset(vis2,,sizeof(vis2));
for(int i=;i<num[];i++)
{
if(!sz[][i]) continue;
int ok=,tot=,cnt=;
for(int j=h[][i];j;j=edge[][j].pre)
{
int cur=c2[edge[][j].to];
if(vis1[cur]) {ok=;break;}
if(!vis2[cur])
{
cnt++;
tot+=sz[][cur];
vis2[cur]=;
}
}
if(sz[][i]!=tot) ok=;
if(ok)
{
if(cnt==) O++;
else S++;
}
for(int j=h[][i];j;j=edge[][j].pre) vis1[c2[edge[][j].to]]=;
}
memset(vis1,,sizeof(vis1));
memset(vis2,,sizeof(vis2));
for(int i=;i<num[];i++)
{
if(!sz[][i]) continue;
int ok=,tot=,cnt=;
for(int j=h[][i];j;j=edge[][j].pre)
{
int cur=c1[edge[][j].to];
if(vis1[cur]) {ok=;break;}
if(!vis2[cur])
{
cnt++;
tot+=sz[][cur];
vis2[cur]=;
}
}
if(ok&&sz[][i]==tot&&cnt>) M++;
for(int j=h[][i];j;j=edge[][j].pre) vis1[c1[edge[][j].to]]=;
}
printf("Case #%d: %d %d %d\n",kase,S,M,O);
}
return ;
}
Aguin
1005 Shape
1006 Removed Interval
1007 Simple Matrix
1008 The Next
1009 Find a path
1010 Queue