Submission #550009

#	Time	Username	Problem	Language	Result	Execution time	Memory
550009		ivan24	Inside information (BOI21_servers)	C++14	50 / 100	432 ms	109072 KiB

servers

#include <bits/stdc++.h>

using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define F first
#define S second

struct qry{
    char type;
    ll x,y;
    qry(){}
};

struct data{
    ll mn, mx;
    bool isup, isdown;
    // isup is increasing, isdown is decreasing
    data(){
        mn = -1; mx = -1; isup = isdown = false;
    }
    data(ll x){
        mn = mx = x;
        isup = isdown = true;
    }
    data merge_data (const data& rhs){
        data res;
        res.mn = min(mn,rhs.mn);
        res.mx = max(mx,rhs.mx);
        res.isup = isup && rhs.isup && (mx < rhs.mn);
        res.isdown = isdown && rhs.isdown && (mn > rhs.mx);
        return res;
    }
    void print(){
        cout << "mn: " << mn << " mx: " << mx << " isup: " << isup << " isdown: " << isdown << "\n";
    }
};

class BinLift {
private:
    vector<vector<data> > bl;
    vvi lca;
    vi p,w,d;
    ll lift (ll v, ll x){
        for (ll i = 0; 20 > i; i++){
            ll bm = 1; bm <<= i;
            if (x & bm) v = lca[i][v];
        }
        return v;
    }
    data bl_lift (ll v, ll x){
        data res;
        for (ll i = 0; 20 > i; i++){
            ll bm = 1; bm <<= i;
            if (x & bm){
                if (res.mn == -1){
                    res = bl[i][v];
                }else{
                    res = bl[i][v].merge_data(res);
                }
                v = lca[i][v];
            }
        }
        return res;
    }
    ll lca_qry (ll u, ll v){
        if (d[u] > d[v]) swap(u,v);
        // d[u] <= d[v]
        // lift v
        v = lift(v,d[v]-d[u]);
        if (v == u) return v;
        for (ll i = 19; i >= 0; i--){
            if (lca[i][v] != lca[i][u]){
                v = lca[i][v];
                u = lca[i][u];
            }
        }
        return p[v];
    }
public:
    BinLift(vi p,vi w,vi d): p(p), w(w), d(d){
        ll n = p.size();
        lca.assign(20,vi(n,-1));
        lca[0] = p;
        bl.assign(20, vector<data>(n));
        for (ll i = 0; n > i; i++){
            bl[0][i] = data(w[i]);
        }

        for (ll i = 1; 20 > i; i++){
            for (ll j = 0; n > j; j++){
                lca[i][j] = lca[i-1][j];
                if (lca[i-1][j] != -1)
                    lca[i][j] = lca[i-1][lca[i-1][j]];
            }
        }

        for (ll i = 1; 20 > i; i++){
            for (ll j = 0; n > j; j++){
                if (lca[i][j] == -1) continue;
                bl[i][j] = bl[i-1][lca[i-1][j]].merge_data(bl[i-1][j]);
            }
        }
    }
    BinLift(){}
    bool qry(ll s, ll e, ll t){
        ll curlca = lca_qry(s,e);
        data res;
        if (curlca == s){
            ll diff = d[e]-d[curlca];
            res = bl_lift(e,diff);
        }else if (curlca == e){
            ll diff = d[s]-d[curlca];
            res = bl_lift(s,diff);
            swap(res.isup, res.isdown);
        }else{
            ll sd = d[s]-d[curlca];
            ll ed = d[e]-d[curlca];

            data sres = bl_lift(s,sd);
            data eres = bl_lift(e,ed);

            swap(sres.isdown,sres.isup);
            res = sres.merge_data(eres);

        }
        //res.print();
        return (res.isdown && res.mx <= t);
    }
};

class Solver{
private:
    ll n,k;
    vector<qry> q;
    vvii adjList;
    vi p,w,d;
    BinLift bl;
    void dfs (ll v){
        for (auto e: adjList[v]){
            if (e.F != p[v]){
                p[e.F] = v; w[e.F] = e.S; d[e.F] = d[v]+1; dfs(e.F);
            }
        }
    }
public:
    Solver(){
        cin >> n >> k;
        adjList.resize(n);
        q.resize(n+k-1);
        ll ctr = 0;
        for (auto &i: q){
            cin >> i.type;
            if (i.type == 'C') cin >> i.x;
            else{
                cin >> i.x >> i.y;
                i.x--; i.y--;
                if (i.type == 'S'){
                    adjList[i.x].emplace_back(i.y,ctr);
                    adjList[i.y].emplace_back(i.x,ctr);
                    ctr++;
                }
            }
        }
        p.assign(n,-1);
        w.assign(n,-1);
        d.assign(n,0);
        dfs(0);
        bl = BinLift(p,w,d);
    }
    void solve(){
        ll ctr = -1;
        for (auto &i: q){
            if (i.type == 'C') cout << "1\n";
            else if (i.type == 'S') ctr++;
            else{
                if (i.x == i.y){
                    cout << "yes\n";
                }else{
                    cout << ((bl.qry(i.x,i.y,ctr) ? "yes" : "no")) << "\n";
                }
            }
        }
    }
};

int main(){
    Solver mySolver;
    mySolver.solve();
}

• 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