oj.uz

답안 #658024

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
658024 2022-11-11T22:41:30 Z Lobo Inside information (BOI21_servers) C++17
50 / 100
 771 ms 148792 KB 
#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];
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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 275 ms 9264 KB Output is correct
2 Correct 375 ms 13968 KB Output is correct
3 Correct 309 ms 14024 KB Output is correct
4 Correct 534 ms 14048 KB Output is correct
5 Correct 430 ms 14256 KB Output is correct
6 Correct 312 ms 13956 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 275 ms 9264 KB Output is correct
2 Correct 375 ms 13968 KB Output is correct
3 Correct 309 ms 14024 KB Output is correct
4 Correct 534 ms 14048 KB Output is correct
5 Correct 430 ms 14256 KB Output is correct
6 Correct 312 ms 13956 KB Output is correct
7 Incorrect 274 ms 9756 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 9312 KB Output is correct
2 Correct 564 ms 138476 KB Output is correct
3 Correct 550 ms 138624 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 9312 KB Output is correct
2 Correct 564 ms 138476 KB Output is correct
3 Correct 550 ms 138624 KB Output is correct
4 Incorrect 316 ms 9752 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 263 ms 9400 KB Output is correct
2 Correct 620 ms 148792 KB Output is correct
3 Correct 637 ms 148780 KB Output is correct
4 Correct 704 ms 148284 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 263 ms 9400 KB Output is correct
2 Correct 620 ms 148792 KB Output is correct
3 Correct 637 ms 148780 KB Output is correct
4 Correct 704 ms 148284 KB Output is correct
5 Incorrect 324 ms 9960 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 9292 KB Output is correct
2 Correct 579 ms 140068 KB Output is correct
3 Correct 538 ms 140452 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 9292 KB Output is correct
2 Correct 579 ms 140068 KB Output is correct
3 Correct 538 ms 140452 KB Output is correct
4 Incorrect 282 ms 9736 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 308 ms 9340 KB Output is correct
2 Correct 558 ms 148792 KB Output is correct
3 Correct 545 ms 148688 KB Output is correct
4 Correct 660 ms 148308 KB Output is correct
5 Correct 242 ms 9904 KB Output is correct
6 Correct 501 ms 139996 KB Output is correct
7 Correct 457 ms 140088 KB Output is correct
8 Correct 647 ms 140892 KB Output is correct
9 Correct 529 ms 140836 KB Output is correct
10 Correct 580 ms 144932 KB Output is correct
11 Correct 746 ms 144236 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 308 ms 9340 KB Output is correct
2 Correct 558 ms 148792 KB Output is correct
3 Correct 545 ms 148688 KB Output is correct
4 Correct 660 ms 148308 KB Output is correct
5 Correct 242 ms 9904 KB Output is correct
6 Correct 501 ms 139996 KB Output is correct
7 Correct 457 ms 140088 KB Output is correct
8 Correct 647 ms 140892 KB Output is correct
9 Correct 529 ms 140836 KB Output is correct
10 Correct 580 ms 144932 KB Output is correct
11 Correct 746 ms 144236 KB Output is correct
12 Incorrect 236 ms 9844 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 241 ms 9236 KB Output is correct
2 Correct 308 ms 14212 KB Output is correct
3 Correct 250 ms 14256 KB Output is correct
4 Correct 347 ms 14416 KB Output is correct
5 Correct 313 ms 14572 KB Output is correct
6 Correct 248 ms 14292 KB Output is correct
7 Correct 227 ms 10032 KB Output is correct
8 Correct 473 ms 138656 KB Output is correct
9 Correct 473 ms 138592 KB Output is correct
10 Correct 240 ms 9544 KB Output is correct
11 Correct 524 ms 148428 KB Output is correct
12 Correct 537 ms 148404 KB Output is correct
13 Correct 660 ms 147620 KB Output is correct
14 Correct 237 ms 9392 KB Output is correct
15 Correct 505 ms 139348 KB Output is correct
16 Correct 449 ms 139636 KB Output is correct
17 Correct 630 ms 140340 KB Output is correct
18 Correct 532 ms 140240 KB Output is correct
19 Correct 592 ms 144292 KB Output is correct
20 Correct 771 ms 143560 KB Output is correct
21 Correct 481 ms 137840 KB Output is correct
22 Correct 491 ms 138660 KB Output is correct
23 Correct 499 ms 138796 KB Output is correct
24 Correct 502 ms 138788 KB Output is correct
25 Correct 566 ms 140836 KB Output is correct
26 Correct 476 ms 138460 KB Output is correct
27 Correct 435 ms 138356 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 241 ms 9236 KB Output is correct
2 Correct 308 ms 14212 KB Output is correct
3 Correct 250 ms 14256 KB Output is correct
4 Correct 347 ms 14416 KB Output is correct
5 Correct 313 ms 14572 KB Output is correct
6 Correct 248 ms 14292 KB Output is correct
7 Correct 227 ms 10032 KB Output is correct
8 Correct 473 ms 138656 KB Output is correct
9 Correct 473 ms 138592 KB Output is correct
10 Correct 240 ms 9544 KB Output is correct
11 Correct 524 ms 148428 KB Output is correct
12 Correct 537 ms 148404 KB Output is correct
13 Correct 660 ms 147620 KB Output is correct
14 Correct 237 ms 9392 KB Output is correct
15 Correct 505 ms 139348 KB Output is correct
16 Correct 449 ms 139636 KB Output is correct
17 Correct 630 ms 140340 KB Output is correct
18 Correct 532 ms 140240 KB Output is correct
19 Correct 592 ms 144292 KB Output is correct
20 Correct 771 ms 143560 KB Output is correct
21 Correct 481 ms 137840 KB Output is correct
22 Correct 491 ms 138660 KB Output is correct
23 Correct 499 ms 138796 KB Output is correct
24 Correct 502 ms 138788 KB Output is correct
25 Correct 566 ms 140836 KB Output is correct
26 Correct 476 ms 138460 KB Output is correct
27 Correct 435 ms 138356 KB Output is correct
28 Incorrect 247 ms 9404 KB Extra information in the output file
29 Halted 0 ms 0 KB -