Expert.
Put your skills to the test.

Problem summary

Maintain an undirected road network. Calls ask whether two towns are connected (type 1), open a road (type 2), or close a road (type 3). Output the answers to all connectivity queries as one bit string.

Source clarification. Arena slug is no122A, but the PDF calls the program no112A and the Bulgarian title is ТЕЛЕФОН 112. Roads are interpreted as undirected, with open/closed status per unordered pair.

Constraints

N ≤ 1000; M ≤ 2N; Q ≤ 100000. The statement describes about 30–35% openings and about one tenth as many closures as openings.

Worked example

Official statement sample.

9 8
1 2
3 4
5 6
7 8
9 5
7 2
8 2
6 9
8
1 1 8
1 6 2
2 7 1
1 4 7
2 2 3
1 4 7
3 3 4
1 4 7

10010

Solution analysis

1. Process the calls offline. For each unordered road pair record each maximal interval of query indices during which it is open. Initially open roads begin at time zero; an opening begins an interval, and a closure ends it immediately before that call.
2. Put each active interval into a segment tree over time. Traverse the tree with a disjoint-set union structure that supports rollback. At a node unite its roads, answer queries at leaves, and undo the node’s merges before returning to its parent. Union by size gives logarithmic find time without path compression.
3. In the sample towns 1 and 8 are initially connected, while 6 and 2 are not. Opening road 2–3 later connects 4 to 7, and closing 3–4 disconnects 4 again, producing 10010.

Why it works

The segment-tree cover places a road on exactly one node of every root-to-leaf path whose time lies in its active interval, and on no other such path. Thus at a leaf the DSU represents exactly the currently open graph. DSU connectivity is exact, and rollback restores the state required by each sibling subtree.

Watch out. Path compression must not be used with this simple rollback log. Normalize road endpoints. Duplicate open/close notifications are treated idempotently.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
using namespace std;
using Edge=pair<int,int>;
struct DSU{
    vector<int>parent,size;
    vector<Edge>history;
    explicit DSU(int n):parent(n+1),size(n+1,1){
        iota(parent.begin(),parent.end(),0);
    }
    int find(int x){
        while(parent[x]!=x){
            x=parent[x];
        }
        return x;
    }
    void unite(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b){
            return;
        }
        if(size[a]<size[b]){
            swap(a,b);
        }
        history.push_back({a,b});
        parent[b]=a;
        size[a]+=size[b];
    }
    void rollback(int checkpoint){
        while(static_cast<int>(history.size())>checkpoint){
            auto[a,b]=history.back();
            history.pop_back();
            size[a]-=size[b];
            parent[b]=b;
        }
    }
};
struct Call{
    int type,x,y;
};
vector<vector<Edge>>tree;
vector<Call>calls;
void insert(int node,int left,int right,int from,int to,Edge e){
    if(from>=right||to<=left){
        return;
    }
    if(from<=left&&right<=to){
        tree[node].push_back(e);
        return;
    }
    int mid=(left+right)/2;
    insert(node*2,left,mid,from,to,e);
    insert(node*2+1,mid,right,from,to,e);
}
void solve(int node,int left,int right,DSU&dsu){
    // Roll back all merges made in this subtree before visiting its sibling.
    int checkpoint=dsu.history.size();
    for(auto[a,b]:tree[node]){
        dsu.unite(a,b);
    }
    if(right-left==1){
        const Call&c=calls[left];
        if(c.type==1){
            cout<<(dsu.find(c.x)==dsu.find(c.y)?'1':'0');
        }
    }
    else{
        int mid=(left+right)/2;
        solve(node*2,left,mid,dsu);
        solve(node*2+1,mid,right,dsu);
    }
    dsu.rollback(checkpoint);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    map<Edge,int>opened;
    while(m--){
        int x,y;
        cin>>x>>y;
        opened[minmax(x,y)]=0;
    }
    int q;
    cin>>q;
    calls.resize(q);
    tree.resize(4*max(1,q));
    for(int i=0;i<q;++i){
        Call&c=calls[i];
        cin>>c.type>>c.x>>c.y;
        Edge e=minmax(c.x,c.y);
        if(c.type==2&&!opened.count(e)){
            opened[e]=i;
        }
        if(c.type==3&&opened.count(e)){
            insert(1,0,q,opened[e],i,e);
            opened.erase(e);
        }
    }
    if(q){
        for(const auto&entry:opened){
            insert(1,0,q,entry.second,q,entry.first);
        }
        DSU dsu(n);
        solve(1,0,q,dsu);
    }
    cout<<'\n';
}