백준18941 평면 그래프와 게임

작성일 | In

문제 링크

  • http://icpc.me/18941

사용 알고리즘

  • 듀얼 그래프

풀이

문제를 한 문장으로 요약하면 Online Decremental Dynamic Connectivity in Planar Graph입니다.

간선을 끊는 쿼리를 먼저 생각해봅시다.
평면 그래프에서는 $V-E+F = C+1$가 성립합니다. 간선을 하나 끊으면 E가 1만큼 감소합니다. 이때 $C$가 증가하기 위해서는 $V, F$ 값에 변동이 없어야 합니다. $V$의 값은 변하지 않으므로 $F$의 값만 봐주면 됩니다.
즉, 간선 하나를 끊었을 때 face의 개수가 줄어든다면 컴포넌트가 분리되지 않은 것이고, face의 개수가 변하지 않았다면 컴포넌트가 분리된 것입니다. face의 개수 변화는 Dual Graph를 이용해 관리해줄 수 있습니다.

두 정점 $u, v$를 간선이 없어지면서 컴포넌트가 분리되었다면 $u$를 포함하는 컴포넌트와 $v$를 포함하는 컴포넌트로 나뉘게 될텐데, small to large처럼 둘 중 크기가 더 작은 쪽에만 색깔을 다시 칠해주면 모든 쿼리에서 최대 $O(N \log N)$번만 색칠하게 됩니다.
즉, 간선을 끊는 쿼리는 amortized $O(\log N)$에 처리할 수 있습니다.

두 정점 $u, v$가 연결되었는지 확인하는 것은 정점의 색깔만 봐주면 되므로 $O(1)$에 처리할 수 있습니다.

크기가 더 작은 쪽에만 색을 칠해주기 위해서는 두 컴포넌트의 크기를 알아야 합니다.
단순하게 DFS/BFS를 돌리면 $O(N^2)$ 당연히 안 되고, 스택/큐에 정점을 하나씩 추가하면서 신중하게 잘 구현해야 합니다.

크기 구할 때 쿼리당 $O(N)$에 구하고 색칠하는 것은 amortized $O(log N)$만에 하는 풀이를 저격하는 데이터가 Star Graph밖에 없기 때문에, 트리일 때는 KOI16 고등부 트리처럼 HLD로 예외처리해주는 풀이가 통과됩니다.
데이터 추가 요청을 넣어놓은 상태입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;
istream& operator >> (istream &in, p &t){ in >> t.x >> t.y; return in; }

ll ccw(const p &a, const p &b, const p &c){
    ll dx1 = b.x - a.x, dy1 = b.y - a.y;
    ll dx2 = c.x - b.x, dy2 = c.y - b.y;
    ll res = dx1*dy2 - dx2*dy1;
    if(res > 0) return 1;
    if(res) return -1;
    return 0;
}

namespace DualGraph{
    const int MV = 101010, ME = 101010; // MAX_V, MAX_E
    p pt[MV];
    vector<p> g[MV]; // g[s].emplace_back(e, edge_id);
    set<p> gph[MV]; // g[s].emplace_back(e, edge_id);
    vector<int> dual_pt;

    // Union Find
    int par[ME * 1];
    void uf_init(){ iota(par, par+ME*2, 0); }
    int find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
    int merge(int u, int v){
        u = find(u); v = find(v);
        if(u == v) return 0;
        par[u] = v; return 1;
    }

    p base;
    bool cmp_angle(const p &_a, const p &_b){
        p a = pt[_a.x], b = pt[_b.x];
        if((a > base) != (b > base)) return a > b;
        return ccw(a, base, b) > 0;
    }

    void addEdge(int s, int e, int id){
        g[s].emplace_back(e, id);
        g[e].emplace_back(s, id);
        gph[s].emplace(e, id); // if use removeEdge
        gph[e].emplace(s, id); // if use removeEdge
    }

    void removeEdge(int s, int e, int id){
        gph[s].erase(gph[s].find(p(e, id)));
        gph[e].erase(gph[e].find(p(s, id)));
    }

    int out; //outer face
    void getDual(int n, int m){
        uf_init();
        for(int i=1; i<=n; i++){
            base = pt[i];
            sort(all(g[i]), cmp_angle);
            // up, left : *2+1
            // down, right : *2
            for(int j=0; j<g[i].size(); j++){
                int k = j ? j - 1 : g[i].size()-1;
                int u = g[i][k].y << 1 | 1, v = g[i][j].y << 1;
                p p1 = pt[g[i][k].x], p2 = pt[g[i][j].x];
                if(p1 > base) u ^= 1;
                if(p2 > base) v ^= 1;
                merge(u, v);
            }
        }
        int mn_idx = min_element(pt+1, pt+n+1) - pt;
        out = find(g[mn_idx][0].y << 1 | 1);

        for(int i=1; i<=m; i++){
            dual_pt.push_back(find(i << 1));
            dual_pt.push_back(find(i << 1 | 1));
        }
        compress(dual_pt);
    }
}

ll n, m, q, X, Y;
map<p, int> mp;
int chk[101010], pv;
int color[101010], col;

void divide(int a, int b){
    pv++; col++;
    vector<p> stk[2];
    vector<int> arr[2];
    stk[0].emplace_back(a, 0);
    stk[1].emplace_back(b, 0);
    while(stk[0].size() && stk[1].size()){
        for(int i=0; i<2; i++){
            int v = stk[i].back().x, c = stk[i].back().y; stk[i].pop_back();
            arr[i].push_back(v); chk[v] = pv;
            auto it = DualGraph::gph[v].lower_bound(p(c, -1));
            if(it == DualGraph::gph[v].end()) continue;
            stk[i].emplace_back(v, it->x + 1);
            if(chk[it->x] != pv) stk[i].emplace_back(it->x, 0);
        }
    }
    if(stk[0].empty()) for(auto i : arr[0]) color[i] = col;
    else for(auto i : arr[1]) color[i] = col;
}

void init(int v){
    color[v] = col;
    for(auto i : DualGraph::g[v]) if(!color[i.x]) init(i.x);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> q >> X >> Y;
    for(int i=1; i<=n; i++) cin >> DualGraph::pt[i];
    for(int i=1; i<=m; i++){
        int s, e; cin >> s >> e;
        if(s > e) swap(s, e);
        DualGraph::addEdge(s, e, i);
        mp[p(s, e)] = i;
    }
    DualGraph::getDual(n, m);

    for(int i=1; i<=n; i++) if(!color[i]) col++, init(i);

    int cnt = 0;
    while(q--){
        int op, a, b; cin >> op >> a >> b;
        a = (a - 1 + cnt * X) % n + 1;
        b = (b - 1 + cnt * Y) % n + 1;
        if(op == 1){
            if(a > b) swap(a, b);
            if(!mp.count(p(a, b))) continue;
            int edge_id = mp[p(a, b)];
            mp.erase(p(a, b));
            DualGraph::removeEdge(a, b, edge_id);
            if(DualGraph::merge(edge_id << 1, edge_id << 1 | 1)) continue;
            divide(a, b);
        }
        else{
            if(color[a] == color[b]) cnt++, cout << "A\n";
            else cout << "D\n";
        }
    }
}