oj.uz

답안 #658021

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
658021 2022-11-11T22:38:06 Z Lobo Inside information (BOI21_servers) C++17
50 / 100
 741 ms 148448 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 == 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:197: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]
  197 |             for(int i = 0; i < ords.size(); i++) {
      |                            ~~^~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 9392 KB Output is correct
2 Correct 307 ms 13688 KB Output is correct
3 Correct 285 ms 13784 KB Output is correct
4 Correct 353 ms 13788 KB Output is correct
5 Correct 399 ms 13996 KB Output is correct
6 Correct 276 ms 13640 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 9392 KB Output is correct
2 Correct 307 ms 13688 KB Output is correct
3 Correct 285 ms 13784 KB Output is correct
4 Correct 353 ms 13788 KB Output is correct
5 Correct 399 ms 13996 KB Output is correct
6 Correct 276 ms 13640 KB Output is correct
7 Incorrect 235 ms 9512 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 9260 KB Output is correct
2 Correct 504 ms 138340 KB Output is correct
3 Correct 489 ms 138532 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 9260 KB Output is correct
2 Correct 504 ms 138340 KB Output is correct
3 Correct 489 ms 138532 KB Output is correct
4 Incorrect 234 ms 9608 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 255 ms 9264 KB Output is correct
2 Correct 604 ms 148448 KB Output is correct
3 Correct 592 ms 148356 KB Output is correct
4 Correct 653 ms 147736 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 255 ms 9264 KB Output is correct
2 Correct 604 ms 148448 KB Output is correct
3 Correct 592 ms 148356 KB Output is correct
4 Correct 653 ms 147736 KB Output is correct
5 Incorrect 232 ms 10212 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 240 ms 9384 KB Output is correct
2 Correct 510 ms 139724 KB Output is correct
3 Correct 463 ms 140088 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 240 ms 9384 KB Output is correct
2 Correct 510 ms 139724 KB Output is correct
3 Correct 463 ms 140088 KB Output is correct
4 Incorrect 232 ms 9508 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 9312 KB Output is correct
2 Correct 547 ms 148280 KB Output is correct
3 Correct 539 ms 148320 KB Output is correct
4 Correct 678 ms 147520 KB Output is correct
5 Correct 264 ms 10228 KB Output is correct
6 Correct 502 ms 142376 KB Output is correct
7 Correct 465 ms 142704 KB Output is correct
8 Correct 669 ms 143424 KB Output is correct
9 Correct 527 ms 143540 KB Output is correct
10 Correct 584 ms 147568 KB Output is correct
11 Correct 731 ms 146844 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 9312 KB Output is correct
2 Correct 547 ms 148280 KB Output is correct
3 Correct 539 ms 148320 KB Output is correct
4 Correct 678 ms 147520 KB Output is correct
5 Correct 264 ms 10228 KB Output is correct
6 Correct 502 ms 142376 KB Output is correct
7 Correct 465 ms 142704 KB Output is correct
8 Correct 669 ms 143424 KB Output is correct
9 Correct 527 ms 143540 KB Output is correct
10 Correct 584 ms 147568 KB Output is correct
11 Correct 731 ms 146844 KB Output is correct
12 Incorrect 227 ms 10168 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 234 ms 9244 KB Output is correct
2 Correct 297 ms 13588 KB Output is correct
3 Correct 251 ms 13768 KB Output is correct
4 Correct 336 ms 13700 KB Output is correct
5 Correct 306 ms 13852 KB Output is correct
6 Correct 243 ms 13616 KB Output is correct
7 Correct 224 ms 9464 KB Output is correct
8 Correct 476 ms 138148 KB Output is correct
9 Correct 471 ms 138148 KB Output is correct
10 Correct 236 ms 9516 KB Output is correct
11 Correct 513 ms 148116 KB Output is correct
12 Correct 513 ms 148248 KB Output is correct
13 Correct 701 ms 147480 KB Output is correct
14 Correct 237 ms 10200 KB Output is correct
15 Correct 506 ms 142300 KB Output is correct
16 Correct 443 ms 142604 KB Output is correct
17 Correct 636 ms 143388 KB Output is correct
18 Correct 513 ms 143308 KB Output is correct
19 Correct 585 ms 147500 KB Output is correct
20 Correct 741 ms 146892 KB Output is correct
21 Correct 483 ms 141360 KB Output is correct
22 Correct 489 ms 142216 KB Output is correct
23 Correct 500 ms 142044 KB Output is correct
24 Correct 535 ms 142284 KB Output is correct
25 Correct 535 ms 144036 KB Output is correct
26 Correct 469 ms 141820 KB Output is correct
27 Correct 430 ms 141924 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 234 ms 9244 KB Output is correct
2 Correct 297 ms 13588 KB Output is correct
3 Correct 251 ms 13768 KB Output is correct
4 Correct 336 ms 13700 KB Output is correct
5 Correct 306 ms 13852 KB Output is correct
6 Correct 243 ms 13616 KB Output is correct
7 Correct 224 ms 9464 KB Output is correct
8 Correct 476 ms 138148 KB Output is correct
9 Correct 471 ms 138148 KB Output is correct
10 Correct 236 ms 9516 KB Output is correct
11 Correct 513 ms 148116 KB Output is correct
12 Correct 513 ms 148248 KB Output is correct
13 Correct 701 ms 147480 KB Output is correct
14 Correct 237 ms 10200 KB Output is correct
15 Correct 506 ms 142300 KB Output is correct
16 Correct 443 ms 142604 KB Output is correct
17 Correct 636 ms 143388 KB Output is correct
18 Correct 513 ms 143308 KB Output is correct
19 Correct 585 ms 147500 KB Output is correct
20 Correct 741 ms 146892 KB Output is correct
21 Correct 483 ms 141360 KB Output is correct
22 Correct 489 ms 142216 KB Output is correct
23 Correct 500 ms 142044 KB Output is correct
24 Correct 535 ms 142284 KB Output is correct
25 Correct 535 ms 144036 KB Output is correct
26 Correct 469 ms 141820 KB Output is correct
27 Correct 430 ms 141924 KB Output is correct
28 Incorrect 222 ms 10096 KB Extra information in the output file
29 Halted 0 ms 0 KB -