2015 ACM/ICPC Asia Regional Hefei Online

两边离散化。暴力扫C就过了。
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 #define maxn 1000010
  7 bool vis1[maxn],vis2[maxn];
  8 int Hash[maxn],h[2][maxn];
  9 int tt[2],num[2],c1[maxn],c2[maxn];
 10 int sz[2][maxn];
 11 
 12 struct node
 13 {
 14     int to,pre;
 15 } edge[2][maxn];
 16 
 17 void add(int op,int from,int to)
 18 {
 19     tt[op]++;
 20     edge[op][tt[op]].pre=h[op][from];
 21     edge[op][tt[op]].to=to;
 22     h[op][from]=tt[op];
 23 }
 24 
 25 int id(int op,int x)
 26 {
 27     return lower_bound(Hash,Hash+num[op],x)-Hash;
 28 }
 29 
 30 int main(void)
 31 {
 32     int T; cin>>T;
 33     for(int kase=1;kase<=T;kase++)
 34     {
 35         memset(tt,0,sizeof(tt));
 36         memset(h,0,sizeof(h));
 37         memset(sz,0,sizeof(sz));
 38         memset(Hash,0,sizeof(Hash));
 39         int n; scanf("%d",&n);
 40         for(int i=0;i<n;i++) scanf("%d%d",c1+i,c2+i);
 41         for(int i=0;i<n;i++) Hash[i]=c1[i];
 42         sort(Hash,Hash+n);
 43         num[0]=unique(Hash,Hash+n)-Hash;
 44         for(int i=0;i<n;i++)
 45         {
 46             add(0,c1[i]=id(0,c1[i]),i);
 47             sz[0][c1[i]]++;
 48         }
 49         for(int i=0;i<n;i++) Hash[i]=c2[i];
 50         sort(Hash,Hash+n);
 51         num[1]=unique(Hash,Hash+n)-Hash;
 52         for(int i=0;i<n;i++)
 53         {
 54             add(1,c2[i]=id(1,c2[i]),i);
 55             sz[1][c2[i]]++;
 56         }
 57         int S=0,M=0,O=0;
 58         memset(vis1,0,sizeof(vis1));
 59         memset(vis2,0,sizeof(vis2));
 60         for(int i=0;i<num[0];i++)
 61         {
 62             if(!sz[0][i]) continue;
 63             int ok=1,tot=0,cnt=0;
 64             for(int j=h[0][i];j;j=edge[0][j].pre)
 65             {
 66                 int cur=c2[edge[0][j].to];
 67                 if(vis1[cur]) {ok=0;break;}
 68                 if(!vis2[cur])
 69                 {
 70                     cnt++;
 71                     tot+=sz[1][cur];
 72                     vis2[cur]=1;
 73                 }
 74             }
 75             if(sz[0][i]!=tot) ok=0;
 76             if(ok)
 77             {
 78                 if(cnt==1) O++;
 79                 else S++;
 80             }
 81             for(int j=h[0][i];j;j=edge[0][j].pre) vis1[c2[edge[0][j].to]]=1;
 82         }
 83         memset(vis1,0,sizeof(vis1));
 84         memset(vis2,0,sizeof(vis2));
 85         for(int i=0;i<num[1];i++)
 86         {
 87             if(!sz[1][i]) continue;
 88             int ok=1,tot=0,cnt=0;
 89             for(int j=h[1][i];j;j=edge[1][j].pre)
 90             {
 91                 int cur=c1[edge[1][j].to];
 92                 if(vis1[cur]) {ok=0;break;}
 93                 if(!vis2[cur])
 94                 {
 95                     cnt++;
 96                     tot+=sz[0][cur];
 97                     vis2[cur]=1;
 98                 }
 99             }
100             if(ok&&sz[1][i]==tot&&cnt>1) M++;
101             for(int j=h[1][i];j;j=edge[1][j].pre) vis1[c1[edge[1][j].to]]=1;
102         }
103         printf("Case #%d: %d %d %d
",kase,S,M,O);
104     }
105     return 0;
106 }
Aguin
1004 Difference of Languages
1005 Shape
1006 Removed Interval
1007 Simple Matrix
1008 The Next
1009 Find a path
1010 Queue