This question isn’t that easy because of its data range..If it had a narrower data range,I could pass every test point TAT. Anyway,you just need to enumerate the status of the first line,then you can know the status of following lines(1 stands for front,0 stands for back).So you just need to enumerate the first line….And use an O(2^20) algorithm to search out all status.

#include <iostream>
#include <time.h>
#include<cstdio>
#include<cstring>

using namespace std;
int b[65536]={0};
int he[105]={0};
int cun[105]={0};
int main()
{
    int a[17];
    a[1]=1;
    for (int i=2;i<=16;i++)
        a[i]=a[i-1]*2;
    int s;
    for (int i=1;i<=65535;i++){
        s=i;
        while (s!=0){
            if (s%2)
                b[i]+=1;
            s/=2;
        }
    }
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF){
        memset(he,0,sizeof(he));
        for (int i=1;i<=n;i++){
            for (int j=m;j>=1;j--){
                scanf("%d",&s);
                he[i]+=a[j]*s;
            }
        }
        int mi,zhi,an;
        mi=1000000000;
        zhi=0;
        bool neng;
        neng=false;
        for (int i=0;i<=a[m+1]-1;i++){
            zhi=b[i];
            cun[1]=(he[1]^i);
            cun[1]=((i*2%a[m+1])^cun[1]);
            cun[1]=((i/2%a[m+1])^cun[1]);
            cun[2]=(he[2]^i);
            for (int j=2;j<=n;j++){
                zhi+=b[a[m+1]-cun[j-1]-1];
                an=a[m+1]-cun[j-1]-1;
                cun[j]=(cun[j]^an);
                cun[j+1]=(he[j+1]^an);
                cun[j]=((an*2%a[m+1])^cun[j]);
                cun[j]=((an/2%a[m+1])^cun[j]);
            }
            if (cun[n]==a[m+1]-1&&zhi<mi){
                mi=zhi;
                neng=true;
            }
        }
        if (neng)
            printf("%dn",mi);
        else
            printf("no solutionn");
    }
    return 0;
}

Lots of participants said Problem B is a piece of cake…Well really easy(Because it is the only problem that I get full score…).U just need to use an Offline Union find to store connected points.And check out them in each query.It is really easy to handle…

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define MaxN 10005
#define MaxM 50005

struct node
{
    int x , y , len;
}a[MaxM];
int UF[MaxN];
int P[MaxN];
int f[MaxM];
int n , m , q;

int cmp(const node&,const node&);
int Find(int);
int binarysearch(int);

int main()
{

    while (scanf("%d%d%d",&n,&m,&q)!=EOF)
    {
        memset(P,0,sizeof(P));
        for (int i=0;i<=n;i++) UF[i] = i;

        for (int i=1;i<=m;i++)
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].len);

        a[0].len = 0;
        a[m+1].len = 0x3fffffff;
        sort(a+1,a+m+1,cmp);
        for (int i=0;i<=n;i++)
            P[i] = 1;

        for (int i=1;i<=m;i++)
        {
            f[i] = f[i-1];
            if (Find(a[i].x)!=Find(a[i].y))
            {
                f[i] += P[Find(a[i].x)]*P[Find(a[i].y)];
                P[Find(a[i].x)] += P[Find(a[i].y)];
                UF[Find(a[i].y)] = Find(a[i].x);
            }
        }
        f[m+1] = 0x3fffffff;

        for (int i=0;i<q;i++)
        {
            int tmp;
            scanf("%d",&tmp);
            printf("%dn",f[binarysearch(tmp)]);
        }
    }
    return    0;
}

int cmp(const node&a,const node&b)
{
    return a.len<b.len;
}

int Find(int x)
{
    if (UF[x] != x)
        UF[x] = Find(UF[x]);
    return    UF[x];
}

int binarysearch(int x)
{
    int s = 0;
    int t = m;
    int ret = (s+t)>>1;

    while (!(a[ret].len<=x&&x<a[ret+1].len))
    {
        if (a[ret].len>x)
            t = ret-1;
        else
            s = ret+1;
        ret = (s+t)>>1;
    }
    return    ret;
}

This is a classic problem in NetWorkFlow section…The MaxFlow problem.I tried to used ISAP to solve this problem but I failed because the data range was too large….I’ll show the AC Code for this problem.

Actually This problem was hard enough to drag my speed during the contest 233333.

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define min(a,b) a<b?a:b

const int maxnode = 101000 + 5;
const int maxedge = 1010000 + 5;
const int oo = 10000000;

int node, src, dest, nedge;
int head[maxnode], dist[maxnode], Q[maxnode], work[maxnode];
int  point[maxedge], Ne[maxedge], flow[maxedge], capa[maxedge];

void init(int _node, int _src, int _dest) {
    node = _node;
    src = _src;
    dest = _dest;
    for (int i = 0; i < node; i++) head[i] = -1;
    nedge = 0;
}

void addedge(int u, int v, int c1, int c2) {
    point[nedge] = v, capa[nedge] = c1, flow[nedge] = 0, Ne[nedge] = head[u], head[u] = (nedge++);
    point[nedge] = u, capa[nedge] = c2, flow[nedge] = 0, Ne[nedge] = head[v], head[v] = (nedge++);
}

bool dinic_bfs() {
    memset(dist, 255, sizeof (dist));
    dist[src] = 0;
    int sizeQ = 0;
    Q[sizeQ++] = src;
    for (int cl = 0; cl < sizeQ; cl++)
        for (int k = Q[cl], i = head[k]; i >= 0; i = Ne[i])
            if (flow[i] < capa[i] && dist[point[i]] < 0) {
                dist[point[i]] = dist[k] + 1;
                Q[sizeQ++] = point[i];
            }
    return dist[dest] >= 0;
}

int dinic_dfs(int x, int exp) {
    if (x == dest) return exp;
    for (int &i = work[x]; i >= 0; i = Ne[i]) {
        int v = point[i], tmp;
        if (flow[i] < capa[i] && dist[v] == dist[x] + 1 && (tmp = dinic_dfs(v, min(exp, capa[i] - flow[i]))) > 0) {
            flow[i] += tmp;
            flow[i^1] -= tmp;
            return tmp;
        }
    }
    return 0;
}

int dinic_flow() {
    int result = 0;
    while (dinic_bfs()) {
        for (int i = 0; i < node; i++) work[i] = head[i];
        while (1) {
            int delta = dinic_dfs(src, oo);
            if (delta == 0) break;
            result += delta;
        }
    }
    return result;
}

int main() {
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
    int sum=0,t;
    init(n+m+2,n+m,n+m+1);
    for (int i=0;i<n;i++) {
        scanf("%d",&t);
        addedge(n+m,i,t,0);
    }
    int a,b,c;
    for (int i=0;i<m;i++) {
        scanf("%d%d%d",&a,&b,&c);
        a--,b--;
        sum+=c;
        addedge(a,i+n,oo,0);
        addedge(b,i+n,oo,0);
        addedge(i+n,n+m+1,c,0);
    }
    printf("%dn",sum-dinic_flow());
    }
    return 0;
}

Oh,my god.Geometric isn’t my strong suit.I didn’t solve this problem..I should say sorry…I’v not learnt that section…I’ll just give out the solution.

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<math.h>
using namespace std;

#define MAXN 110
#define EPS 1e-8

typedef long long llint;

double transformMat[4][4];

struct point3D{
    double x,y,z;
    point3D():x(0.0),y(0.0),z(0.0){;}
    point3D(double xx,double yy,double zz):x(xx),y(yy),z(zz){;}
    point3D operator +(const point3D &p)
    {
        point3D resP(x+p.x,y+p.y,z+p.z);
        return resP;
    }
    point3D operator -(const point3D &p)
    {
        point3D resP(x-p.x,y-p.y,z-p.z);
        return resP;
    }
    point3D operator *(const double &lamda)
    {
        point3D resP(x*lamda,y*lamda,z*lamda);
        return resP;
    }
    double dot(const point3D &p)
    {
        return x*p.x+y*p.y+z*p.z;
    }
    point3D cross(const point3D &p)
    {
        point3D resP;
        resP.x=y*p.z-z*p.y;
        resP.y=z*p.x-x*p.z;
        resP.z=x*p.y-y*p.x;
        return resP;
    }
    double mag()
    {
        return sqrt(x*x+y*y+z*z);
    }
    void normalize()
    {
        double m=mag();
        x/=m;
        y/=m;
        z/=m;
    }
};

typedef point3D vec3D;

struct plane{
    double a,b,c,d;
    void init()
    {
        double mag=vec3D(a,b,c).mag();
        a/=mag;
        b/=mag;
        c/=mag;
        d/=mag;
    }
};

void multMat(double MA[][4],double MB[][4])
{
    double MR[4][4];
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
            MR[i][j]=0.0;
    }

    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            for(int k=0;k<4;k++)
                MR[i][j]+=MA[i][k]*MB[k][j];
        }
    }
    memcpy(MB,MR,sizeof(MR));
}

void loadIdentity(double mat[][4])
{
    for(int i=0;i<4;i++)
    {
        mat[i][i]=1.0;
        for(int j=0;j<4;j++)
        {
            if(i==j)continue;
            mat[i][j]=0.0;
        }
    }
}

void translate(double tx,double ty,double tz)
{
    double tmpMat[4][4];
    loadIdentity(tmpMat);
    tmpMat[0][3]=tx;
    tmpMat[1][3]=ty;
    tmpMat[2][3]=tz;
    multMat(tmpMat,transformMat);
}

void rotate(double theta,double vx,double vy,double vz)
{
    double tmpMat[4][4];
    double cosTheta2=cos(theta/2.0),sinTheta2=sin(theta/2.0);
    tmpMat[0][0]=1.0-2.0*(vy*vy+vz*vz)*sinTheta2*sinTheta2;
    tmpMat[1][0]=2.0*vx*vy*sinTheta2*sinTheta2+2.0*vz*cosTheta2*sinTheta2;
    tmpMat[2][0]=2.0*vx*vz*sinTheta2*sinTheta2-2.0*vy*cosTheta2*sinTheta2;
    tmpMat[3][0]=0.0;

    tmpMat[0][1]=2.0*vx*vy*sinTheta2*sinTheta2-2.0*vz*cosTheta2*sinTheta2;
    tmpMat[1][1]=1.0-2.0*(vx*vx+vz*vz)*sinTheta2*sinTheta2;
    tmpMat[2][1]=2.0*vy*vz*sinTheta2*sinTheta2+2.0*vx*cosTheta2*sinTheta2;
    tmpMat[3][1]=0.0;

    tmpMat[0][2]=2.0*vx*vz*sinTheta2*sinTheta2+2.0*vy*cosTheta2*sinTheta2;
    tmpMat[1][2]=2.0*vy*vz*sinTheta2*sinTheta2-2.0*vx*cosTheta2*sinTheta2;
    tmpMat[2][2]=1.0-2.0*(vx*vx+vy*vy)*sinTheta2*sinTheta2;
    tmpMat[3][2]=0.0;

    tmpMat[0][3]=tmpMat[1][3]=tmpMat[2][3]=0.0;
    tmpMat[3][3]=1.0;

    multMat(tmpMat,transformMat);
}

int n,m;
plane P;
double a,b,c,d;
point3D S[MAXN],R[MAXN];
point3D C[MAXN];
point3D O;
point3D bp;
bool isEqualD(double d1,double d2)
{
    return fabs(d1-d2)<EPS;
}

void transform(double trMat[][4],point3D &p)
{
    point3D resP;
    resP.x=trMat[0][0]*p.x+trMat[0][1]*p.y+trMat[0][2]*p.z+trMat[0][3];
    resP.y=trMat[1][0]*p.x+trMat[1][1]*p.y+trMat[1][2]*p.z+trMat[1][3];
    resP.z=trMat[2][0]*p.x+trMat[2][1]*p.y+trMat[2][2]*p.z+trMat[2][3];
    p=resP;
}

bool isInter(point3D o,point3D s,double &lamda)
{
    vec3D tv=s-o;
    if(isEqualD(tv.z,0.0))
        return false;
    lamda=-(o.z/tv.z);
    return lamda>EPS;
}

double cross(point3D p1,point3D p2,point3D p3)
{
    double res=0.0;
    return (p2-p1).x*(p3-p1).y-(p2-p1).y*(p3-p1).x;
}


bool cmp(point3D p1,point3D p2)
{
    llint kross=cross(bp,p1,p2);
    if(kross==0)
        return (p1-bp).mag()<(p2-bp).mag();
    return kross>0;
}

int GrahamScan(point3D *pts,int n)
{
    int i,j,k;
    llint u,v;
    for(i=0,k=0;i<n;i++)
    {
        u=pts[i].x-pts[k].x;
        v=pts[i].y-pts[k].y;
        if((u<0)||(u==0&&v<0))k=i;
    }
    bp=pts[k];
    sort(pts,pts+n,cmp);
    pts[n]=pts[0];
    for(i=1,j=2;j<n;j++)
    {
        while(i>0&&cross(pts[i-1],pts[i],pts[j])<=0)
            i--;
        pts[++i]=pts[j];
    }
    return i+1;
}

bool isInPolygon(point3D *pts,int n,point3D p)
{
    for(int i=0;i<n;i++)
    {
        if(cross(pts[i],pts[(i+1)%n],p)<EPS)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    int ta,tb,tc,td;
    while(scanf("%d %d %d %d",&ta,&tb,&tc,&td),!(!ta&&!tb&&!tc&&!td))
    {
        P.a=ta,P.b=tb,P.c=tc,P.d=td;
        P.init();
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%lf %lf %lf",&S[i].x,&S[i].y,&S[i].z);

        scanf("%lf %lf %lf",&O.x,&O.y,&O.z);

        scanf("%d",&m);
        for(int i=0;i<m;i++)
            scanf("%lf %lf %lf",&R[i].x,&R[i].y,&R[i].z);

        loadIdentity(transformMat);
        translate(-P.a*P.d,-P.b*P.d,-P.c*P.d);
        vec3D tmpV=vec3D(P.a,P.b,P.c).cross(vec3D(0.0,0.0,1.0));
        double cosTheta=vec3D(P.a,P.b,P.c).dot(vec3D(0.0,0.0,1.0));
        if(!isEqualD(fabs(cosTheta),1.0))
        {
            tmpV.normalize();
            rotate(acos(cosTheta),tmpV.x,tmpV.y,tmpV.z);
        }

        for (int i=0;i<n;i++)
        {
            transform(transformMat,S[i]);
        }
        transform(transformMat,O);

        for(int i=0;i<m;i++)
        {
            transform(transformMat,R[i]);
        }
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            double lamda;
            if(isInter(O,S[i],lamda))
            {
                C[cnt++]=O+(S[i]-O)*lamda;
            }
        }

        if(cnt==0)
        {
            printf("ZEROn");
            continue;
        }
        else if(cnt!=n)
        {
            printf("INFn");
            continue;
        }
        else
        {
            cnt=GrahamScan(C,cnt);
            int ans=0;
            for(int i=0;i<m;i++)
            {
                double lamda;
                if(!isInter(O,R[i],lamda))
                    continue;
                R[i]=O+(R[i]-O)*lamda;
                if(isInPolygon(C,cnt,R[i]))
                {
                    ans++;
                }
            }
            printf("%.2lf%%n",(double)ans/m*100);
            continue;
        }

    }

    return 0;
}