Submission #411591

#	Time	Username	Problem	Language	Result	Execution time	Memory
411591		Aldas25	Inside information (BOI21_servers)	C++14	50 / 100	302 ms	54024 KiB

servers

//#pragma GCC optimize ("03")
//#pragma GCC optimize ("0fast")
//#pragma GCC optimize ("02")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target ("avx2")

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vl;

const int MAXN = 500100, MAXK = 20;

int n, k;
vector<pair<char, pii>> queries;

vii adj[MAXN];
int par[MAXN][MAXK];
int dep[MAXN];
int longMaz[MAXN], longDid[MAXN];
int mx[MAXN][MAXK];

void dfs (int v, int p, int fr = 0) {
    FOR(i, 1, MAXK-1) {
        par[v][i] = par[par[v][i-1]][i-1];
        mx[v][i] = max(mx[v][i-1], mx[par[v][i-1]][i-1]);
    }

    for (auto pp : adj[v]) {
        int u = pp.f;
        int cnt = pp.s;
        if (u == p) continue;

        dep[u] = dep[v]+1;
        par[u][0] = v;
        mx[u][0] = cnt;

        longMaz[u] = longDid[u] = 1;
        if (cnt < fr) longDid[u] = longDid[v] + 1;
        else longMaz[u] = longMaz[v] + 1;

        dfs (u, v, cnt);
    }
}

int lift (int v, int d) {
    FOR(i, 0, MAXK-1)
        if (d & (1<<i))
            v = par[v][i];
    return v;
}

int lca (int u, int v) {
    if (u == v) return u;
    if (dep[u] < dep[v])swap(u,v);
    int d = dep[u] - dep[v];
    FOR(i, 0, MAXK-1)
        if (d & (1<<i))
            u = par[u][i];
    if (u == v) return u;

    for (int i = MAXK-1; i >= 0; i--) {
        if (par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    }

    return par[u][0];
}

int getMx (int u, int v) {
    if (u == v) return 0;
    int ret = 0;
    if (dep[u] < dep[v])swap(u,v);
    int d = dep[u] - dep[v];
    FOR(i, 0, MAXK-1) {
        if (d & (1<<i)) {
            ret = max(ret, mx[u][i]);
            u = par[u][i];
        }
    }

    if (u == v) return ret;

    for (int i = MAXK-1; i >= 0; i--) {
        if (par[u][i] != par[v][i]) {
            ret = max(ret, mx[v][i]);
            ret = max(ret, mx[u][i]);
            u = par[u][i];
            v = par[v][i];
        }
    }

    ret = max(ret, mx[v][0]);
    ret = max(ret, mx[u][0]);

    return ret;
}

bool query (int a, int d, int t) {
    if (a == d) return true;
    if (getMx(a, d) > t) return false;

    swap(a,d);

    int anc = lca(a, d);
    //cout << " "
    if (longDid[a] >= dep[a]-dep[anc] && longMaz[d] >= dep[d]-dep[anc]) {
            //cout << " h  ere" << endl;
        int cnt1 = 0, cnt2 = 0;

        if (a == anc || d == anc) return true;

        int a1 = lift(a, dep[a]-dep[anc]-1);
        int d1 = lift(d, dep[d]-dep[anc]-1);

        cnt1 = mx[a1][0];
        cnt2 = mx[d1][0];

        //cout << " a= " << a << " d= " << d << " cnt1 = " << cnt1 << " cnt2 = " << cnt2 << endl;
        //cout << "  a1 = " << a1 << " d1 = " << d1 << endl;
        //cout << "  anc = " << anc << " depa = " << dep[a] << " depd= " << dep[d] << " depanc = " <<dep[anc] << endl;

        if (cnt1 < cnt2) return true;

        return false;
    }

    return false;
}

void share (int u, int v) {

}

int qCount (int d) {
    return 1;
}

int main()
{
    FAST_IO;

    cin >> n >> k;
    //FOR(i, 1, n) nodes[i].insert(i);
    //FOR(i, 1, n) cntN[i] ++;
    FOR(cnt, 1, n+k-1) {
        char c;
        cin >> c;
        int a, b = 0;
        if (c == 'S') cin >> a >> b;
        else if (c == 'Q') cin >> a >> b;
        else cin >> a;
        queries.pb({c, {a,b}});

        if (c == 'S') {
               // cnt++;
            adj[a].pb({b, cnt});
            adj[b].pb({a, cnt});
        }
    }

    dfs (1, -1 );

    int cnt = 0;
    for (auto q : queries) {
        cnt++;
        if (q.f == 'S') {
            share(q.s.f, q.s.s);
            continue;
        }

        if (q.f == 'Q') {
            if (query (q.s.f, q.s.s, cnt)) cout << "yes\n";
            else cout << "no\n";
        } else {
            cout << qCount(q.s.f) << "\n";
        }
    }

    return 0;
}

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