제출 #657457

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
657457		Lobo	Inside information (BOI21_servers)	C++17	50 / 100	762 ms	143364 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++) {
        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));
        }
        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);
        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;


    }
}

컴파일 시 표준 에러 (stderr) 메시지

servers.cpp: In function 'int32_t main()':
servers.cpp:132: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]
  132 |         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