Submission #2998494


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

Submission Time
Task D - みんな仲良し高橋君
User hitonanode
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4689 Byte
Status WA
Exec Time 1022 ms
Memory 74220 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 3
AC × 10
WA × 5
AC × 30
WA × 18
Set Name Test Cases
Sample example_0.txt, example_1.txt, example_2.txt
Subtask1 bone_bubun_0.txt, bone_bubun_1.txt, bone_bubun_2.txt, komakai_bubun_0.txt, komakai_bubun_1.txt, komakai_bubun_2.txt, maxrand_bubun_0.txt, maxrand_bubun_1.txt, random_bubun_0.txt, random_bubun_1.txt, smallrand_bubun_0.txt, smallrand_bubun_1.txt, smallrand_bubun_2.txt, square_bubun_0.txt, square_bubun_1.txt
All bone_0.txt, bone_1.txt, bone_2.txt, bone_bubun_0.txt, bone_bubun_1.txt, bone_bubun_2.txt, example_0.txt, example_1.txt, example_2.txt, handmade_0.txt, handmade_1.txt, handmade_2.txt, handmade_3.txt, komakai_0.txt, komakai_1.txt, komakai_2.txt, komakai_bubun_0.txt, komakai_bubun_1.txt, komakai_bubun_2.txt, maxrand_0.txt, maxrand_1.txt, maxrand_bubun_0.txt, maxrand_bubun_1.txt, random_0.txt, random_1.txt, random_bubun_0.txt, random_bubun_1.txt, renket_0.txt, renket_1.txt, smallrand_0.txt, smallrand_1.txt, smallrand_bubun_0.txt, smallrand_bubun_1.txt, smallrand_bubun_2.txt, square_0.txt, square_1.txt, square_bubun_0.txt, square_bubun_1.txt, supersmall_0.txt, supersmall_1.txt, threeren_0.txt, threeren_1.txt, treebase_0.txt, treebase_1.txt, treebase_2.txt, example_0.txt, example_1.txt, example_2.txt
Case Name Status Exec Time Memory
bone_0.txt WA 821 ms 58152 KB
bone_1.txt WA 812 ms 57768 KB
bone_2.txt WA 845 ms 57512 KB
bone_bubun_0.txt AC 152 ms 17200 KB
bone_bubun_1.txt AC 16 ms 2432 KB
bone_bubun_2.txt AC 230 ms 23280 KB
example_0.txt AC 1 ms 256 KB
example_1.txt AC 1 ms 256 KB
example_2.txt AC 1 ms 256 KB
handmade_0.txt AC 1 ms 256 KB
handmade_1.txt AC 1 ms 256 KB
handmade_2.txt AC 1 ms 256 KB
handmade_3.txt AC 1 ms 256 KB
komakai_0.txt WA 922 ms 56940 KB
komakai_1.txt WA 930 ms 59244 KB
komakai_2.txt WA 897 ms 58732 KB
komakai_bubun_0.txt WA 842 ms 74220 KB
komakai_bubun_1.txt WA 792 ms 70380 KB
komakai_bubun_2.txt WA 813 ms 70252 KB
maxrand_0.txt AC 1022 ms 53484 KB
maxrand_1.txt AC 998 ms 53484 KB
maxrand_bubun_0.txt AC 770 ms 61036 KB
maxrand_bubun_1.txt AC 791 ms 61676 KB
random_0.txt AC 21 ms 2048 KB
random_1.txt AC 502 ms 31344 KB
random_bubun_0.txt AC 23 ms 2560 KB
random_bubun_1.txt WA 187 ms 17524 KB
renket_0.txt WA 864 ms 59116 KB
renket_1.txt WA 881 ms 58860 KB
smallrand_0.txt AC 2 ms 256 KB
smallrand_1.txt AC 2 ms 256 KB
smallrand_bubun_0.txt AC 1 ms 256 KB
smallrand_bubun_1.txt AC 1 ms 256 KB
smallrand_bubun_2.txt WA 1 ms 256 KB
square_0.txt AC 658 ms 66024 KB
square_1.txt AC 661 ms 68456 KB
square_bubun_0.txt AC 643 ms 68840 KB
square_bubun_1.txt AC 464 ms 54892 KB
supersmall_0.txt AC 1 ms 256 KB
supersmall_1.txt AC 1 ms 256 KB
threeren_0.txt WA 799 ms 50412 KB
threeren_1.txt WA 829 ms 54124 KB
treebase_0.txt WA 712 ms 52076 KB
treebase_1.txt WA 129 ms 12276 KB
treebase_2.txt WA 489 ms 40556 KB