Submission #2998516

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)


struct UnionFind
{
    vector<int> par, rank;
    UnionFind(int N) {
        par = rank = vector<int>(N, 0);
        REP(i, N) par[i] = i;
    }
    int find(int x) { return (par[x] == x) ? x : (par[x] = find(par[x])); }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) par[x] = y;
        else par[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
    }
    bool same(int x, int y) { return find(x) == find(y); }
};


struct UndirectedGraph
{
    using pint = pair<int, int>;

    int V; // 頂点数
    int E; // 辺の数
    int k;
    vector<vector<pint>> to;
    vector<pint> edges;

    vector<int> order, lowlink; // lowlink
    vector<bool> isusedforDFS; // 各辺がDFS木に参加しているか
    vector<bool> is_art; // 各点が関節点か

    vector<vector<int> > bvc_edges; // 二連結成分分解後の全辺の分類

    vector<int> num_child;

    UndirectedGraph(int V) : V(V), E(0), k(0), to(vector<vector<pint>>(V)) {}

    void add_edge(int v1, int v2)
    {
        to[v1].push_back(pint(v2, E));
        to[v2].push_back(pint(v1, E));
        edges.push_back(pint(v1, v2));
        E++;
    }

    vector<int> edge_stack;
    int root_now;
    int _dfs_lowlink(int now, int prev = -1)
    {
        if (prev == -1) root_now = k;
        order[now] = lowlink[now] = k;
        k++;

        for (auto nxt : to[now]) if (nxt.first != prev)
        {
            if (order[nxt.first] < order[now]) edge_stack.push_back(nxt.second);
            if (order[nxt.first] < 0)
            {
                isusedforDFS[nxt.second] = 1;
                num_child[now] += _dfs_lowlink(nxt.first, now);
                lowlink[now] = min(lowlink[now], lowlink[nxt.first]);

                if ((order[now] == root_now && order[nxt.first] != root_now+1) || 
                    (order[now] != root_now && lowlink[nxt.first] >= order[now])) is_art[now] = 1;

                if (lowlink[nxt.first] >= order[now])
                {
                    bvc_edges.push_back(vector<int>());
                    while (1)
                    {
                        int edge = edge_stack.back();
                        int v1 = edges[edge].first;
                        int v2 = edges[edge].second;
                        edge_stack.pop_back();
                        bvc_edges.back().push_back(edge);
                        if (min(v1, v2) == min(now, nxt.first) && max(v1, v2) == max(now, nxt.first)) break;
                    }
                }
            } else lowlink[now] = min(lowlink[now], order[nxt.first]);
        }
        return num_child[now] + 1;
    }

    void build_lowlink()
    {
        order.assign(V, -1);
        lowlink.assign(V, -1);
        isusedforDFS.assign(E, 0);
        is_art.assign(V, false);
        bvc_edges.clear();
        num_child.assign(V, 0);
        for (int i = 0; i < V; i++) if (order[i] < 0) _dfs_lowlink(i);
    }
};



int main()
{
    int N;
    cin >> N;

    UndirectedGraph graph(2 * N + 1);
    UnionFind uf(2 * N + 1);
    map<int, vector<int>> xlst[2];
    REP(i, 2 * N + 1)
    {
        int x, y;
        cin >> x >> y;
        xlst[0][x - 1].push_back(i);
        xlst[1][y - 1].push_back(i);
    }

    REP(d, 2) for (auto pa : xlst[d])
    {
        int len = pa.second.size();
        REP(i, len - 1) uf.unite(pa.second[i], pa.second[i + 1]);
        REP(i, len - 1) graph.add_edge(pa.second[i], pa.second[i + 1]);
        REP(i, len - 2) graph.add_edge(pa.second[i], pa.second[i + 2]);
    }

    graph.build_lowlink();
    map<int, int> group_size;
    REP(i, 2 * N + 1) group_size[uf.find(i)]++;

    int odd = -1;
    for (auto pa : group_size) if (pa.second & 1)
    {
        if (odd < 0) odd = pa.first;
        else
        {
            REP(i, 2 * N + 1) cout << "NG" << endl;
            return 0;
        }
    }

    REP(i, 2 * N + 1) {
        bool flg = true;
        if (odd != uf.find(i)) flg = false;
        if (graph.is_art[i])
        {
            for (auto nxt : graph.to[i]) if (graph.lowlink[nxt.first] >= graph.order[i] && graph.isusedforDFS[nxt.second])
            {
                if (!(graph.num_child[nxt.first] & 1)) flg = false;
            }
        }
        cout << (flg ? "OK" : "NG") << endl;
    }
}

Submission Info

Judge Result