【LOJ】#2084. 「NOI2016」网格

题解

之前用的mapTLE了，今天用了个hash把题卡了过去，AC数++

我们只要保留一个点为中心周围5 * 5个格子就可以

如果一个点周围5*5个格子有两个不连通，那么显然输出0

如果一个出现了一个割点，那么看看这个割点在不在离中心点的第一层，如果在的话就是1，没有合法割点的话就是2

然后就是特判了……特判真的挺多的……

代码

#include <bits/stdc++.h>

//#define ivorysi

#define MAXN 100005

#define mo 974711

#define INF 1000000000000000000LL

#define pii pair<int,int>

#define fi first

#define se second

using namespace std;

typedef long long int64;

pii poi[MAXN * 26];

vector<int> V[MAXN],st;

int N,M,c,cnt,T;

struct Hash {

    struct node {

        int64 x;int next,c;

    }E[MAXN * 26];

    int head[mo + 5],sumE;

    void clear() {

        sumE = 0;memset(head,0,sizeof(head));

    }

    void add(int64 x,int c) {

        int u = x % mo;

        E[++sumE].x = x;E[sumE].next = head[u];E[sumE].c = c;head[u] = sumE;

    }

    void Insert(pii x,int c) {

        add(1LL * (x.fi - 1) * M + x.se,c);

    }

    int Query(pii x) {

        int u = (1LL * (x.fi - 1) * M + x.se) % mo;

        for(int i = head[u] ; i ; i = E[i].next) {

            if(E[i].x == 1LL * (x.fi - 1) * M + x.se) return E[i].c;

        }

        return -1;

    }

}H;

int dx[] = {0,0,1,-1};

int dy[] = {1,-1,0,0};

struct node {

    int to,next;

}edge[MAXN * 100];

int head[MAXN * 26],sumE,low[MAXN * 26],dfn[MAXN * 26],idx,col[MAXN * 26],tot;

bool fir[MAXN * 26];

void dfs(int u,int fa) {

    dfn[u] = low[u] = ++idx;

    col[u] = tot;

    int son = 0;

    for(int i = head[u] ; i ; i = edge[i].next) {

	int v = edge[i].to;

	if(v != fa) {

	    if(dfn[v]) low[u] = min(low[u],dfn[v]);

	    else {

		++son;

		dfs(v,u);

		low[u] = min(low[u],low[v]);

		if(fa != 0 && low[v] >= dfn[u]) {

		    st.push_back(u);

		}

	    }

	}

    }

    if(!fa && son > 1) st.push_back(u);

}

void add(int u,int v) {

    edge[++sumE].to = v;

    edge[sumE].next = head[u];

    head[u] = sumE;

}

void Init() {

    sumE = 0;

    for(int i = 1 ; i <= cnt ; ++i) {

	head[i] = dfn[i] = low[i] = col[i] = fir[i] = tot = idx = 0;

    }

    H.clear();

    int u,v;

    for(int i = 1 ; i <= c ; ++i) {

	scanf("%d%d",&u,&v);

	poi[i] = make_pair(u,v);

	H.Insert(poi[i],i);

    }

    cnt = c;

    for(int i = 1 ; i <= c ; ++i) {

	V[i].clear();

	for(int x = -2 ; x <= 2 ; ++x) {

	    for(int y = -2 ; y <= 2 ; ++y) {

		if(x == 0 && y == 0) continue;

		pii tmp = make_pair(poi[i].fi + x,poi[i].se + y);

		if(tmp.fi < 1 || tmp.fi > N || tmp.se < 1 || tmp.se > M) continue;

		if(H.Query(tmp) == -1) {

		    poi[++cnt] = tmp;

		    H.Insert(poi[cnt],cnt);

		}

		if(x <= 1 && x >= -1 && y <= 1 && y >= -1) fir[H.Query(tmp)] = 1;

		V[i].push_back(H.Query(tmp));

	    }

	}

    }

    for(int i = c + 1 ; i <= cnt ; ++i) {

	for(int j = 0 ; j <= 3 ; ++j) {

	    pii tmp = make_pair(poi[i].fi + dx[j],poi[i].se + dy[j]);

        if(tmp.fi < 1 || tmp.fi > N || tmp.se < 1 || tmp.se > M) continue;

	    int x = H.Query(tmp);

	    if(x <= c) continue;

	    add(i,x);

	}

    }

}

void Solve() {

    scanf("%d",&T);

    while(T--) {

	scanf("%d%d%d",&N,&M,&c);

	Init();

	if(1LL * N * M - c <= 1) {puts("-1");goto again;}

	if(c == 0) {

	    if(1LL * N * M == 2) puts("-1");

	    else if(N == 1 || M == 1) puts("1");

	    else puts("2");

	    goto again;

	}

	st.clear();

	for(int i = c + 1 ; i <= cnt ; ++i) {

	    if(!dfn[i]) {

		++tot;

		dfs(i,0);

	    }

	}

	for(int i = 1 ; i <= c ; ++i) {

	    int t = 0;

	    for(auto k : V[i]) {

		if(k <= c) continue;

		if(k > c) {

		    if(t == 0) t = col[k];

		    else if(t != col[k]) {

			puts("0");

			goto again;

		    }

		}

	    }

	}

	if(1LL * N * M - c == 2) {puts("-1");goto again;}

	for(auto k : st) {

	    if(fir[k]) {puts("1");goto again;}

	}

	if(M == 1 || N == 1) puts("1");

	else puts("2");

        again:;

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}

巴特西

【LOJ】#2084. 「NOI2016」网格

题解

代码

最新文章

热门文章