Submission #658025

#	Time	Username	Problem	Language	Result	Execution time	Memory
658025		Lobo	Inside information (BOI21_servers)	C++17	50 / 100	826 ms	150348 KiB

servers

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()

const int inf = 1e9+10;
const int maxn = 3e5+10;

int n, k, h[maxn];
int pp[maxn][25], pmn[maxn][25], pmx[maxn][25], pin[maxn][25], pde[maxn][25];
int dp[maxn];
vector<pair<int,int>> g[maxn];

void dfs(int u, int ant) {
    for(int i = 1; i <= 20; i++) {
        if(pp[u][i-1] == -1) {
            pp[u][i] = -1;
            pmn[u][i] = pmn[u][i-1];
            pmx[u][i] = pmx[u][i-1];
            pin[u][i] = pin[u][i-1];
            pde[u][i] = pde[u][i-1];
        }
        else {
            pp[u][i] = pp[pp[u][i-1]][i-1];
            pmn[u][i] = min(pmn[u][i-1],pmn[pp[u][i-1]][i-1]);
            pmx[u][i] = max(pmx[u][i-1],pmx[pp[u][i-1]][i-1]);

            pde[u][i] = pde[u][i-1]&pde[pp[u][i-1]][i-1]&(pmn[u][i-1] > pmx[pp[u][i-1]][i-1]);
            pin[u][i] = pin[u][i-1]&pin[pp[u][i-1]][i-1]&(pmx[u][i-1] < pmn[pp[u][i-1]][i-1]);
        }
    }

    for(auto V : g[u]) if(V.fr != ant) {
        int v = V.fr;
        int w = V.sc;
        pmn[v][0] = w;
        pmx[v][0] = w;
        pin[v][0] = 1;
        pde[v][0] = 1;
        pp[v][0] = u;
        h[v] = h[u]+1;
        dfs(v,u);
    }
}

int lca(int u, int v) {
    if(h[v] > h[u]) {
        swap(u,v);
    }

    for(int i = 20; i >= 0; i--) {
        if(pp[u][i] != -1 && h[pp[u][i]] >= h[v]) u = pp[u][i];
    }

    if(u == v) return u;

    for(int i = 20; i >= 0; i--) {
        if(pp[u][i] != -1 && pp[v][i] != -1 && pp[u][i] != pp[v][i]) {
            u = pp[u][i];
            v = pp[v][i];
        }
    }
    return pp[u][0];
}

int32_t main() {
    // freopen("in.in", "r", stdin);
    cin >> n >> k;
    vector<pair<pair<int,int>,pair<int,int>>> qrys;
    for(int i = 1; i <= n+k-1; i++) {
        char op; cin >> op;
        if(op == 'S') {
            int u,v;cin >> u >> v;
            g[u].pb(mp(v,i));
            g[v].pb(mp(u,i));
            qrys.pb(mp(mp(0,i),mp(u,v)));
        }
        else if(op == 'Q') {
            int u,v; cin >> u >> v;
            qrys.pb(mp(mp(1,i),mp(u,v)));
        }
        else if(op == 'C') {
            int v; cin >> v;
            qrys.pb(mp(mp(2,i),mp(v,0)));
        }
    }

    pp[1][0] = -1;
    pmn[1][0] = inf;
    pmx[1][0] = -inf;
    pin[1][0] = 1;
    pde[1][0] = 1;
    dfs(1,1);

    for(int i = 1; i <= n; i++) dp[i] = 1;

    for(auto X : qrys) {
        int optp = X.fr.fr;
        // if(optp == 0) {
        //     int u = X.sc.fr;
        //     int v = X.sc.sc;
        //     if(h[v] < h[u]) swap(u,v);
        //     // u is parent of v

        //     int p = v;
        //     int antw = inf;
        //     while(pp[p][0] != -1 && pmn[p][0] < antw) {
        //         antw = pmn[p][0];
        //         p = pp[p][0];
        //     }

        //     // p is the lowest ancestor of v that v...p is decreacing, so u...p can reach v

        //     int x = v;
        //     while(x != p) {
        //         x = pp[x][0];
        //         dp[x]+= 1;
        //     }

        //     // cout << "  " << u << " " << v << endl;
        //     // for(int i = 1; i <= n; i++) {
        //     //     cout << i << " " << dp[i] << endl;
        //     // }
        // }
        // if(optp == 2) {
        //     int v = X.sc.fr;
        //     int w = X.fr.sc;

        //     int p = v;
        //     int antw = 0;
        //     while(pp[p][0] != -1 && pmx[p][0] < w && pmn[p][0] > antw) {
        //         antw = pmn[p][0];
        //         p = pp[p][0];
        //     }

        //     int x = v;
        //     int ans = 0;
        //     antw = 0;
        //     while(h[x] >= h[p] && x != -1) {
        //         ans++;
        //         for(auto S : g[x]) if(S.fr != pp[x][0]) {
        //             int s = S.fr;
        //             int w1 = S.sc;
        //             if(w1 > antw) {
        //                 ans+= dp[s];
        //             }
        //         }
        //         antw = pmx[x][0];
        //         x = pp[x][0];
        //     }

        //     cout << ans << endl;
        // }
        if(optp == 2) cout << 1 << endl;
        if(optp == 1) {
            int w = X.fr.sc;
            int u = X.sc.sc;
            int v = X.sc.fr;

            int lc = lca(u,v);
            string ans = "yes";

            vector<int> ordu, ordv, ords;
            // while(u != lc) {
            //     ordu.pb(pmn[u][0]);
            //     u = pp[u][0];
            // }
            for(int i = 20; i >= 0; i--) {
                if(pp[u][i] != -1 && h[pp[u][i]] >= h[lc]) {
                    if(pin[u][i] == 0) ans = "no";
                    ordu.pb(pmn[u][i]);
                    ordu.pb(pmx[u][i]);
                    u = pp[u][i];
                }
            }

            // while(v != lc) {
            //     ordv.pb(pmn[v][0]);
            //     v = pp[v][0];
            // }
            for(int i = 20; i >= 0; i--) {
                if(pp[v][i] != -1 && h[pp[v][i]] >= h[lc]) {
                    if(pde[v][i] == 0) ans = "no";
                    ordv.pb(pmx[v][i]);
                    ordv.pb(pmn[v][i]);
                    v = pp[v][i];
                }
            }

            for(auto x : ordu) ords.pb(x);
            reverse(all(ordv));
            for(auto x : ordv) ords.pb(x);

            for(int i = 0; i < ords.size(); i++) {
                if(ords[i] > w) ans = "no";
                if(i != 0 && ords[i] < ords[i-1]) ans = "no";
            }
            cout << ans << endl;
        }
    }

}

Compilation message (stderr)

servers.cpp: In function 'int32_t main()':
servers.cpp:198:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |             for(int i = 0; i < ords.size(); i++) {
      |                            ~~^~~~~~~~~~~~~

• 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