(Live Archive) 6902 - Three Squares

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4914

binary search + greedy

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cassert>
#include <iomanip>
#include <bitset>
using namespace std;

typedef long long      LL;
typedef long double    ld;
typedef pair<int,int>  pii;
typedef pair<LL,LL>    pLL;
typedef vector<int>    vint;
typedef vector<LL>     vLL;
typedef vector<pii>    vpii;
typedef vector<pLL>    vpLL;

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL);
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL,(f)*1LL);

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)

#define IOS ios::sync_with_stdio(0); cin.tie(0);

int myRnd() {
    return abs(  ((rand()<<15) ^ rand()) );
}

int myRnd(int L,int R) {
    return abs(( (rand()<<15)^rand() ) ) % (R-L+1) + L;
}

void Parr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++) {
        printf("%d%c",arr[i]," \n"[i==R]);
    }
}

void Pvec(vint v) {
    for (int i=0;SZ(v)>i;i++) {
        printf("%d%c",v[i]," \n"[i==SZ(v)-1]);
    }
}

void Sarr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++)
    {
        Si(arr[i]);
    }
}

const int N = 1e5 + 6;

const int INF = 1000000000 + 7;

int a[N];

int n;

bool can(int r1,int c1,int r2,int c2,int l,set<pii> st)
{
    //(r1,c1) and (r2,c2) must be smallest
    for (pii p:st)
    {
        if (( !(p.F - r1 > l || p.F - r1 < 0) ) && ( !(p.S - c1 > l || p.S - c1 < 0) )) ;
        else if (( !(p.F - r2 > l || p.F - r2 < 0) ) && ( !(p.S - c2 > l || p.S - c2 < 0) )) ;
        else return false;
    }
    return true;
}

bool can_2(set<pii> st,int l)
{
    if (SZ(st) <= 2) return true;
    int mx_x = -INF,mx_y = -INF,mn_x = INF,mn_y = INF;
    for (pii p:st)
    {
        mx_x = max(mx_x,p.F);
        mx_y = max(mx_y,p.S);
        mn_x = min(mn_x,p.F);
        mn_y = min(mn_y,p.S);
    }
    return can(mn_x,mn_y,mx_x-l,mx_y-l,l,st) || can(mn_x,mx_y-l,mx_x-l,mn_y,l,st);
}

void eerase(set<pii> &st,int r1,int c1,int l)
{
    vpii tmp;
    for (pii p:st)
    {
        if (( !(p.F - r1 > l || p.F - r1 < 0) ) && ( !(p.S - c1 > l || p.S - c1 < 0) )) tmp.PB(p);
    }
    for (pii p:tmp)
    {
        st.erase(st.find(p));
    }
}

bool check(set<pii> st,int l)
{
    int mx_x = -INF,mx_y = -INF,mn_x = INF,mn_y = INF;
    for (pii p:st)
    {
        mx_x = max(mx_x,p.F);
        mx_y = max(mx_y,p.S);
        mn_x = min(mn_x,p.F);
        mn_y = min(mn_y,p.S);
    }
    int dx[4] = {mn_x,mx_x-l,mn_x,mx_x-l},dy[4] = {mn_y,mn_y,mx_y-l,mx_y-l};
    for (int i=0;4>i;i++)
    {
        int tmpx=dx[i],tmpy=dy[i];
        set<pii> st2=st;
        eerase(st2,tmpx,tmpy,l);
        if (can_2(st2,l)) return true;
    }
    return false;
}

int main () {
    srand(time(NULL));
    int T;
    Si(T);
    while (T--)
    {
        Si(n);
        set<pii> st;
        REP1(i,n)
        {
            int x,y;
            Sii(x,y);
            st.insert(MP(x,y));
        }
        n = SZ(st);
        if(n <= 3)
        {
            puts("0");
            continue;
        }
        int L=0,R= 2e9 + 6;
        while (R-L != 1)
        {
            int mid=(L+R)>>1;
            if (check(st,mid)) R = mid;
            else L=mid;
        }
        Pi(R);
    }
}

(Live Archive) 3820 - Mr. Thompson's Problem [一般圖最大匹配，縮花演算法，O(n^4)]

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1821

縮花演算法~

請參考： http://www.csie.ntnu.edu.tw/~u91029/Matching.html#5

My code:

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <set>
using namespace std;

struct Blossom_n4 {
    static const int MAX_N = 206;
    bool adj[MAX_N][MAX_N];
    int n;
    void init(int n) {
        this->n = n;
        memset(adj,0,sizeof(adj));
    }
    void add_edge(int u,int v) {
        adj[u][v] = adj[v][u] = 1;
    }
    int m[MAX_N];  //matching point
    //if m[i] == i --> deleted point
    deque<int> path[MAX_N];  //path from root, only stored even point
    int d[MAX_N];  //odd point or even point
    //0 --> even, 1-->odd, -1--<non-visited
    #define SZ(x) ((int)(x).size())
    queue<int> que;
    void label(int u,int v,int lca_id) {
        for (int i=lca_id+1;SZ(path[u])>i;i++) {
            int now=path[u][i];
            if (d[now] == 1) {
                d[now] = 0;
                que.push(now);
                path[now] = path[v];
                path[now].insert(path[now].end(),path[u].rbegin(),path[u].rend()-i);
            }
        }
    }
    bool BFS(int root) {
        for (int i=0;n>=i;i++) {
            path[i].clear();
        }
        while (!que.empty()) que.pop();
        memset(d,-1,sizeof(d));
        d[root] = 0;
        que.push(root);
        path[root].push_back(root);
        while (SZ(que)) {
            int v=que.front();
            que.pop();
            for (int u=0;n>u;u++) {
                if (adj[v][u] && m[u] != u) {
                    //have edges
                    if (d[u] == -1) {
                        if (m[u] == -1) {
                            //oh great
                            //we can update the alternation path!!!
                            for (int i=0;SZ(path[v])-1>i;i+=2) {
                                m[path[v][i]] = path[v][i+1];
                                m[path[v][i+1]] = path[v][i];
                            }
                            m[u] = v;
                            m[v] = u;
                            return true;
                        }
                        else {
                            //oh no
                            //but we find one more even point
                            int uu=m[u];
                            path[uu] = path[v];
                            path[uu].push_back(u);
                            path[uu].push_back(uu);
                            d[u] = 1;
                            d[uu] = 0;
                            que.push(uu);
                        }
                    }
                    else if (d[u] == 1) {
                        //find an odd point
                        //do nothing
                    }
                    else if (d[u] == 0) {
                        //oh jizz
                        //we find a crossing edge
                        //more even points are allowed
                        int lca_id = 0;
                        while (lca_id < SZ(path[u]) && lca_id < SZ(path[v]) && 
                               path[u][lca_id] == path[v][lca_id]) {
                            lca_id++;
                        }
                        lca_id--;
                        label(u,v,lca_id);
                        label(v,u,lca_id);
                    }
                }
            }
        }
        return false;
    }
    int matching() {
        memset(m,-1,sizeof(m));
        int ret=0;
        for (int i=0;n>i;i++) {
            if (m[i] == -1) {
                if (BFS(i)) {
                    ret++;
                }
                else {
                    m[i] = i;
                }
            }
        }
        return ret;
    }
} sagiri;

const int MAX_N = 206;
int a[MAX_N],b[MAX_N];

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int i=0;n>i;i++) {
            scanf("%d",&a[i]);
        }
        set<int> st;
        for (int j=0;m>j;j++) {
            scanf("%d",&b[j]);
            st.insert(b[j]);
        }
        sagiri.init(n);
        for (int i=0;n>i;i++) {
            for (int j=i+1;n>j;j++) {
                if (st.find(a[i]+a[j]) != st.end()) {
                    sagiri.add_edge(i,j);
                }
            }
        }
        printf("%d\n",sagiri.matching());
    }
}