Submission #751469

#	Time	Username	Problem	Language	Result	Execution time	Memory
751469		vjudge1	Inside information (BOI21_servers)	C++17	2.50 / 100	204 ms	46808 KiB

servers

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 120'000;
const int logn = 20;

/*int par[1 + maxn];
int sz[1 + maxn];

void make_set(int a) {
    par[a] = a;
    sz[a] = 1;
}

int find_set(int a) {
    if(a == par[a]) {
        return a;
    }
    return par[a] = find_set(par[a]);
}

void union_sets(int a, int b) {
    a = find_set(a), b = find_set(b);
    if(sz[a] < sz[b]) {
        swap(a, b);
    }
    sz[b] += sz[a];
    par[a] = b;
}*/
/*
int tree[1 + 4 * maxn];

void update(int v, int vl, int vr, int pos, int val) {
    if(vl == vr) {
        tree[v] = val;
        return;
    }
    int mid = (vl + vr) / 2;
    if(pos <= mid) {
        update(2 * v, vl, mid, pos, val);
    } else {
        update(2 * v + 1, mid + 1, vr, pos, val);
    }
    tree[v] = tree[2 * v] + tree[2 * v + 1];
}

int query(int v, int vl, int vr, int ql, int qr) {
    if(vl > qr || vr < ql) {
        return 0;
    }
    if(vl == ql && vr == qr) {
        return tree[v];
    }
    int mid = (vl + vr) / 2;
    return query(2 * v, vl, mid, ql, min(qr, mid)) +
        query(2 * v + 1, mid + 1, vr, max(ql, mid + 1), qr);
}
*/

struct query {
    int t;
    int a, b;
};

int n, q;
vector<query> queries;

vector<pii > ori_graph[1 + maxn];
int par[1 + maxn];
int parwei[1 + maxn];
int depth[1 + maxn];

void dfs(int cur) {
    for(pii nei : ori_graph[cur]) {
        if(nei.fi != par[cur]) {
            par[nei.fi] = cur;
            parwei[nei.fi] = nei.se;
            depth[nei.fi] = depth[cur] + 1;
            dfs(nei.fi);
        }
    }
}

int lift[1 + maxn][logn];
int maxlift[1 + maxn][logn];
int minlift[1 + maxn][logn];
bool increase[1 + maxn][logn];
bool decrease[1 + maxn][logn];

int lca(int a, int b) {
    if(depth[a] < depth[b]) {
        swap(a, b);
    }
    for(int j = logn - 1; j >= 0; j--) {
        if(depth[b] + (1 << j) <= depth[a]) {
            a = lift[a][j];
        }
    }
    for(int j = logn - 1; j >= 0; j--) {
        if(lift[a][j] != lift[b][j]) {
            a = lift[a][j];
            b = lift[b][j];
        }
    }
    a = lift[a][0];
    b = lift[b][0];
    return a; // = b
}

bool qry(int t, int a, int b) {
    if(a == b) {
        return true; // to avoid edge cases
    }
    int c = lca(a, b);
    int maxi = 0;
    vector<pii > from_b, from_a;
    for(int j = logn - 1; j >= 0; j--) {
        //cout << j << " " << depth[b] << " " << depth[c] << "\n";
        //cout << b << " " << c << "\n";
        if(depth[b] >= depth[c] + (1 << j)) {
            if(!increase[b][j]) {
                //cout << "1\n";
                return false;
            }
            from_b.pb({minlift[b][j], maxlift[b][j]});
            b = lift[b][j];
        }
    }
    for(int j = logn - 1; j >= 0; j--) {
        if(depth[a] >= depth[c] + (1 << j)) {
            if(!decrease[a][j]) {
                //cout << "2\n";
                return false;
            }
            from_a.pb({minlift[a][j], maxlift[a][j]});
            a = lift[a][j];
        }
    }
    reverse(from_a.begin(), from_a.end());
    //cout << from_a.size() << " " << from_b.size() << "\n";
    for(pii p : from_a) {
        from_b.pb(p);
    }
    for(int i = 0; i + 1 < from_b.size(); i++) {
        if(from_b[i].se > from_b[i + 1].fi) {
            //cout << "3\n";
            return false;
        }
    }
    //cout << "here" << endl;
    if(from_b.back().se > /*maxi*/t) {
        //cout << "4\n";
        return false;
    }
    return true;
}

void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n + q - 1; i++) {
        string type;
        cin >> type;
        int a, b;
        cin >> a >> b;
        if(type == "S") {
            ori_graph[a].pb({b, i});
            ori_graph[b].pb({a, i});
        }
        if(type == "Q") {
            queries.pb({i, a, b});
        }
    }
    par[1] = 1;
    dfs(1);
    for(int i = 1; i <= n; i++) {
        lift[i][0] = par[i];
        maxlift[i][0] = minlift[i][0] = parwei[i];
        increase[i][0] = decrease[i][0] = true;
    }
    minlift[1][0] = 3 * maxn; // thats basically infinite in this case
    for(int j = 1; j < logn; j++) {
        for(int i = 1; i <= n; i++) {
            int between = lift[i][j - 1];
            lift[i][j] = lift[between][j - 1];
            maxlift[i][j] = max(maxlift[i][j - 1], maxlift[between][j - 1]);
            minlift[i][j] = min(minlift[i][j - 1], minlift[between][j - 1]);
            increase[i][j] = increase[i][j - 1] && increase[between][j - 1]
                && (maxlift[i][j - 1] < minlift[between][j - 1]);
            decrease[i][j] = decrease[i][j - 1] && decrease[between][j - 1]
                && (minlift[i][j - 1] > maxlift[between][j - 1]);
        }
    }
    for(query curq : queries) {
        int t = curq.t, a = curq.a, b = curq.b;
        cout << (qry(t, a, b) ? "yes" : "no") << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

/*
6 3
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
*/

/*
5 10
Q 1 1
Q 1 2
Q 2 1
S 1 2
Q 1 2
Q 2 1
Q 2 3
Q 3 2
S 1 4
Q 2 4
Q 4 2
S 1 5
Q 5 4
S 1 3
*/

Compilation message (stderr)

servers.cpp: In function 'bool qry(int, int, int)':
servers.cpp:149:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for(int i = 0; i + 1 < from_b.size(); i++) {
      |                    ~~~~~~^~~~~~~~~~~~~~~
servers.cpp:120:9: warning: unused variable 'maxi' [-Wunused-variable]
  120 |     int maxi = 0;
      |         ^~~~

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5