Submission #657451

#	Time	Username	Problem	Language	Result	Execution time	Memory
657451		Lobo	Inside information (BOI21_servers)	C++17	15 / 100	3599 ms	122124 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 = 2e5+10;

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

void dfs(int u, int ant) {
    for(int i = 1; i <= 20; i++) {
        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]);

        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;
        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(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] != 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));
        }
        else if(op == 'Q') {
            int u,v; cin >> u >> v;
            qrys.pb(mp(mp(0,i),mp(u,v)));
        }
    }

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

    for(auto X : qrys) {
        int w = X.fr.sc;
        int u = X.sc.sc;
        int v = X.sc.fr;

        int lc = lca(u,v);

        vector<int> ordu, ordv, ords;
        while(u != lc) {
            ordu.pb(pmn[u][0]);
            u = pp[u][0];
        }

        while(v != lc) {
            ordv.pb(pmn[v][0]);
            v = pp[v][0];
        }

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

        string ans = "yes";
        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:104:26: 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]
  104 |         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: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 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