Submission #675691

#	Time	Username	Problem	Language	Result	Execution time	Memory
675691		stanislavpolyn	Inside information (BOI21_servers)	C++17	5 / 100	157 ms	40252 KiB

servers

#include <bits/stdc++.h>

#define fr(i, a, b) for (int i = (a); i <= (b); i++)
#define rf(i, a, b) for (int i = (a); i >= (b); i--)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

using namespace std;

mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template <typename T>
bool umn(T& a, T b) {
    return a > b ? a = b, 1 : 0;
}
template <typename T>
bool umx(T& a, T b) {
    return a < b ? a = b, 1 : 0;
}

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;

const int N = 3e5 + 5;

#define dec abcd

int n, k;
ve<pii> g[N];
ve<array<int, 3>> Q;

int timer;
int tin[N], tout[N];
int up[N][20];
int par[N], val[N];

bool inc[N][20];
bool dec[N][20];
int dep[N];

void dfs(int v = 1, int p = 0) {
    up[v][0] = p;
    fr (i, 1, 19) up[v][i] = up[up[v][i - 1]][i - 1];
    tin[v] = timer++;

    fe (to, g[v]) {
        if (to.fi == p) continue;
        par[to.fi] = v;
        val[to.fi] = to.se;
        dep[to.fi] = dep[v] + 1;
        dfs(to.fi, v);
    }

    tout[v] = timer;
}

bool isUpper(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tin[b];
}

int getLCA(int a, int b) {
    if (isUpper(a, b)) return a;
    if (isUpper(b, a)) return b;
    rf (i, 19, 0) {
        if (up[a][i] && !isUpper(up[a][i], b)) {
            a = up[a][i];
        }
    }
    return up[a][0];
}

int goUp(int v, int d) {
    rf (i, 19, 0) {
        if (d - pw(i) >= 0) {
            v = up[v][i];
            d -= pw(i);
        }
    }
    assert(v);
    return v;
}

bool checkInc(int v, int d) {
    int p = __lg(d);
    return inc[v][p] && inc[goUp(v, d - pw(p))][p];
}


bool checkDec(int v, int d) {
    int p = __lg(d);
    return dec[v][p] && dec[goUp(v, d - pw(p))][p];
}

int getLastEdge(int a, int b) {
    if (isUpper(a, b)) {
        return val[b];
    }
    if (isUpper(b, a)) {
        int v = goUp(a, dep[a] - dep[b] - 1);
        return val[v];
    }
    return val[b];
}

int checkPath(int a, int b) {
    if (isUpper(a, b)) {
        return checkDec(b, dep[b] - dep[a]);
    }
    if (isUpper(b, a)) {
        return checkInc(a, dep[a] - dep[b]);
    }
    int c = getLCA(a, b);
    return checkInc(a, dep[a] - dep[c]) && checkDec(b, dep[b] - dep[c]);
}

int main() {
#ifndef LOCAL
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
#else
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
#endif

    cin >> n >> k;

    int cnt = 0;
    fr (i, 1, n + k - 1) {
        char c;
        cin >> c;
        if (c == 'S') {
            int a, b;
            cin >> a >> b;

            g[a].pb({b, i});
            g[b].pb({a, i});

            // cout << a << " " << b << " " << i << "\n";
        }
        if (c == 'Q') {
            int a, d;
            cin >> a >> d;
            Q.pb({i, a, d});
        }
        if (c == 'C') {
            int x;
            cin >> x;
            Q.pb({i, x, -1});
        }
    }

    dfs();

    fr (i, 1, n) {
        if (par[i]) {
            dec[i][0] = 1;
            inc[i][0] = 1;
        }
    }

    fr (p, 1, 19) {
        fr (i, 1, n) {
            if (up[i][p] && inc[i][p - 1] && inc[up[i][p - 1]][p - 1]) {
                if (val[goUp(i, pw(p - 1) - 1)] < val[up[i][p - 1]]) {
                    inc[i][p] = 1;
                }
            }

            if (up[i][p] && dec[i][p - 1] && dec[up[i][p - 1]][p - 1]) {
                if (val[goUp(i, pw(p - 1) - 1)] > val[up[i][p - 1]]) {
                    dec[i][p] = 1;
                }
            }
        }
    }

    fe (cur, Q) {
        if (cur[2] != -1) {

            if (cur[2] == cur[1]) {
                cout << "yes\n";
                continue;
            }
            // cout << "CHECK PATH " << cur[2] << " " << cur[1] << " " << "t: " << cur[0] << "\n"; 
            // cout << "Last edge: " << getLastEdge(cur[2], cur[1]) << "\n";
            if (checkPath(cur[2], cur[1]) && getLastEdge(cur[2], cur[1]) < cur[0]) {
                cout << "yes\n";
            } else {
                cout << "no\n";
            }
        }
    }

    return 0;
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:149:9: warning: unused variable 'cnt' [-Wunused-variable]
  149 |     int cnt = 0;
      |         ^~~

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 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