let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

explanation.md

Tóm tắt đề

Cho đồ thị có hướng N đỉnh, M cạnh, các đỉnh đánh số từ 1 đến N và Q truy vấn. Mỗi truy vấn có dạng như sau:

  • 1 x d: Thêm một đỉnh N+1 vào đồ thị
    • Nếu d = 1, thêm cạnh nối từ N+1 đến x
    • Nếu d = 0, thêm cạnh nối từ x đến N+1
  • 2 x y: In Yes nếu có đường đi từ x đến y, No trong trường hợp ngược lại. Giới hạn:
  • \[1 <= N, M <= 5 \times 10^4\]
  • \[1 <= Q <= 10^5\]
  • Số đỉnh của đồ thị luôn không vượt quá \(10^4\)

Cách giải

  • Đọc hết các truy vấn, thêm tất cả các cạnh trong truy vấn vào đồ thị đã cho.
  • Tạo đồ thị mới bằng cách gộp tất cả những cạnh nằm trong cùng một thành phần liên thông lại với nhau. Đồ thị mới có dạng DAG (đồ thị có hướng không chu trình).
  • Với mỗi đỉnh u trong DAG, ta tính bitset \(dp[u]\) với ý nghĩa \(dp[u][v] = 1\) nếu có đường đi từ đỉnh u đến đỉnh v.
  • Với mỗi truy vấn x y, tìm 2 đỉnh tương ứng u v trong DAG, xuất Yes nếu \(dp[u][v] = 1\).
main.cpp
Open in Github Download
#include <bitset>
#include <vector>
#include <cstdio>
#include <memory>
#include <limits>
#include <algorithm>
using namespace std;

struct edge { int u, v; };
typedef vector< vector<int> > dsk;
typedef vector< bitset<50000> > bset;

inline void minimize(int &u, int v) { if (u > v) u = v; }

void tj(int i, int &num, const dsk &ke, vector<int> &map, vector<int>& idx, vector<int> &low, int &index, vector<int> &stack) {
    if (idx[i] >= 0) return;
    idx[i] = low[i] = index++;
    stack.push_back(i);
    for (auto j: ke[i]) {
        if (idx[j] < 0) {
            tj(j, num, ke, map, idx, low, index, stack);
            minimize(low[i], low[j]);
        } else if (map[j] < 0) minimize(low[i], idx[j]);
    }
    if (idx[i] == low[i]) {
        int j;
        do {
            j = stack.back(); stack.pop_back();
            map[j] = num;
        } while (j != i);
        num++;
    }
}

dsk* dag(vector<edge> &&canh, int &n, vector<int>& map, bset &set) {
    map.resize(n, -1);
    vector<int> idx(n, -1), low(n, numeric_limits<int>::max());
    vector<int> stack; stack.reserve(n);
    dsk ke(n);
    for (auto&x: canh) ke[x.u].push_back(x.v);
    int num = 0;
    int index = 0;
    for (int i=0; i<n; i++) tj(i, num, ke, map, idx, low, index, stack);
    n = num;
    set.resize(n);
    for (int i=0; i<n; i++) set[i].set(i);
    auto res = new dsk(n);
    for (auto&x: canh) {
        int a = map[x.u], b = map[x.v];
        if (!set[a].test(b)) {
            set[a].set(b);
            (*res)[a].push_back(b);
        }
    }
    return res;
}

void dfs(int i, vector<bool>& visited, bset &set, const dsk *ke) {
    if (visited[i]) return;
    visited[i] = true;
    for (auto j: (*ke)[i]) {
        dfs(j, visited, set, ke);
        set[i] |= set[j];
    }
}

void compute(const dsk *ke, bset &set) {
    int n = (int)ke->size();
    vector<bool> visited(n, false);
    for (int i=0; i<n; i++) dfs(i, visited, set, ke);
}

int main() {
    int m, n; scanf("%d%d", &n, &m);
    vector<edge> canh(m);
    while (m--) scanf("%d%d", &canh[m].u, &canh[m].v);
    vector<edge> query;
    int Q; scanf("%d", &Q);
    query.reserve(Q);
    canh.reserve(Q);
    while (Q--) {
        int t, a, b;
        scanf("%d%d%d", &t, &a, &b);
        if (t & 1) {
            n++;
            if (b & 1) canh.push_back({n, a});
            else canh.push_back({a, n});
        } else query.push_back({a, b});
    }
    for (auto&x: canh) x.u--, x.v--;
    for (auto&x: query) x.u--, x.v--;
    vector<int> map;
    bset set;
    auto ke = dag(move(canh), n, map, set);
    compute(ke, set);
    string output; output.reserve(query.size() * 4);
    for (auto&x: query) {
        int a = map[x.u], b = map[x.v];
        if (set[a].test(b)) output += "Yes\n";
        else output += "No\n";
    }
    printf("%s", output.data());
    delete ke;
    return 0;
}
origin.cpp
Open in Github Download
// Problem setter's code

#include <bits/stdc++.h>
#include <stdio.h>
#include <cstdio>
#define pb push_back
#define mp make_pair
#define sz(s) ((int)(s.size()))
#define all(s) s.begin(),s.end()
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define dbg(x) cerr << (#x) << " --> " << (x) << nxtl;
#define onlycin ios_base::sync_with_stdio(false); cin.tie(0) 

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

const int MAXN = (int)5e5+228;
const char nxtl = '\n';
const int mod = (int)1e9+7;
const double eps = (double)1e-9;
template<typename T> inline bool updmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<typename T> inline bool updmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}
#define y1 qwert
#define y2 trewq
#define x1 asdfg
#define x2 gfdsa
#define left _left
#define right _right

bitset <50005> dp[50005];
bool have[MAXN];
int n, m;
vector < int > g[MAXN], gr[MAXN];
int type[MAXN], from[MAXN], go[MAXN], sz, wh[MAXN];
vector < int > ts;
bool used[MAXN];
vector < int > cmps[MAXN];
vector < pair < int, int > > edge;

void dfs(int x) {
    used[x] = 1;
    for(auto &to : g[x]) if(!used[to])
        dfs(to);
    ts.pb(x);
}
void dfs1(int x) {
    used[x] = 1;
    wh[x] = sz;
    cmps[sz].pb(x);
    for(auto &to : gr[x]) if(!used[to])
        dfs1(to);
}
bool res[MAXN];

int main() {
#ifdef accepted
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    onlycin;
    cin >> n >> m;
    rep(i,1,m) {
        int x, y; cin >> x >> y;
        assert(x >= 1 && x <= n);
        assert(y >= 1 && y <= n);
        edge.pb(mp(x,y));
        g[x].pb(y);
        gr[y].pb(x);
    }
    int q; cin >> q;
    rep(i,1,q) {
        cin >> type[i] >> from[i] >> go[i];
        assert(from[i] <= n);
        if(type[i] == 1) {
            n++;
            if(go[i]) {
                edge.pb(mp(n,from[i]));
                g[n].pb(from[i]);
                gr[from[i]].pb(n);
            } else {
                assert(from[i] >= 1 && from[i] <= n);
                edge.pb(mp(from[i],n));
                g[from[i]].pb(n);
                gr[n].pb(from[i]);
            }
        } else assert(go[i] >= 1 && go[i] <= n);
    }
    assert(n <= 50000);
    rep(i,1,n) if(!used[i]) dfs(i);
    reverse(all(ts));
    memset(used,0,sizeof used);
    for(auto &to : ts) {
        if(!used[to]) {
            sz++;
            dfs1(to);
        }
    }
    rep(i,1,n) g[i].clear();
    for(auto &to : edge) {
        if(wh[to.first] != wh[to.second]) g[wh[to.first]].pb(wh[to.second]);
    }
    memset(used,0,sizeof used);
    rep(i,1,sz) {
        if(!used[i]) {
            dfs(i);
        }
    }
    for(auto &to : ts) {
        dp[to].set(to,1);
        for(auto &it : g[to]) dp[to] |= dp[it];
    }
    per(i,q,1) {
        if(type[i] == 1) {
            n--;
        } else {
            if(go[i] > n || from[i] > n) continue;
            res[i] = dp[wh[from[i]]].test(wh[go[i]]);
        }
    }
    rep(i,1,q) {
        if(type[i] == 1) continue;
        if(res[i]) cout << "Yes\n";
        else cout << "No\n";
    }

    return 0;
}
Comments