oj.uz

Submission #550009

# Submission time Handle Problem Language Result Execution time Memory
550009 2022-04-17T04:35:42 Z ivan24 Inside information (BOI21_servers) C++14
50 / 100
 432 ms 109072 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define F first
#define S second

struct qry{
    char type;
    ll x,y;
    qry(){}
};

struct data{
    ll mn, mx;
    bool isup, isdown;
    // isup is increasing, isdown is decreasing
    data(){
        mn = -1; mx = -1; isup = isdown = false;
    }
    data(ll x){
        mn = mx = x;
        isup = isdown = true;
    }
    data merge_data (const data& rhs){
        data res;
        res.mn = min(mn,rhs.mn);
        res.mx = max(mx,rhs.mx);
        res.isup = isup && rhs.isup && (mx < rhs.mn);
        res.isdown = isdown && rhs.isdown && (mn > rhs.mx);
        return res;
    }
    void print(){
        cout << "mn: " << mn << " mx: " << mx << " isup: " << isup << " isdown: " << isdown << "\n";
    }
};

class BinLift {
private:
    vector<vector<data> > bl;
    vvi lca;
    vi p,w,d;
    ll lift (ll v, ll x){
        for (ll i = 0; 20 > i; i++){
            ll bm = 1; bm <<= i;
            if (x & bm) v = lca[i][v];
        }
        return v;
    }
    data bl_lift (ll v, ll x){
        data res;
        for (ll i = 0; 20 > i; i++){
            ll bm = 1; bm <<= i;
            if (x & bm){
                if (res.mn == -1){
                    res = bl[i][v];
                }else{
                    res = bl[i][v].merge_data(res);
                }
                v = lca[i][v];
            }
        }
        return res;
    }
    ll lca_qry (ll u, ll v){
        if (d[u] > d[v]) swap(u,v);
        // d[u] <= d[v]
        // lift v
        v = lift(v,d[v]-d[u]);
        if (v == u) return v;
        for (ll i = 19; i >= 0; i--){
            if (lca[i][v] != lca[i][u]){
                v = lca[i][v];
                u = lca[i][u];
            }
        }
        return p[v];
    }
public:
    BinLift(vi p,vi w,vi d): p(p), w(w), d(d){
        ll n = p.size();
        lca.assign(20,vi(n,-1));
        lca[0] = p;
        bl.assign(20, vector<data>(n));
        for (ll i = 0; n > i; i++){
            bl[0][i] = data(w[i]);
        }

        for (ll i = 1; 20 > i; i++){
            for (ll j = 0; n > j; j++){
                lca[i][j] = lca[i-1][j];
                if (lca[i-1][j] != -1)
                    lca[i][j] = lca[i-1][lca[i-1][j]];
            }
        }

        for (ll i = 1; 20 > i; i++){
            for (ll j = 0; n > j; j++){
                if (lca[i][j] == -1) continue;
                bl[i][j] = bl[i-1][lca[i-1][j]].merge_data(bl[i-1][j]);
            }
        }
    }
    BinLift(){}
    bool qry(ll s, ll e, ll t){
        ll curlca = lca_qry(s,e);
        data res;
        if (curlca == s){
            ll diff = d[e]-d[curlca];
            res = bl_lift(e,diff);
        }else if (curlca == e){
            ll diff = d[s]-d[curlca];
            res = bl_lift(s,diff);
            swap(res.isup, res.isdown);
        }else{
            ll sd = d[s]-d[curlca];
            ll ed = d[e]-d[curlca];

            data sres = bl_lift(s,sd);
            data eres = bl_lift(e,ed);

            swap(sres.isdown,sres.isup);
            res = sres.merge_data(eres);

        }
        //res.print();
        return (res.isdown && res.mx <= t);
    }
};

class Solver{
private:
    ll n,k;
    vector<qry> q;
    vvii adjList;
    vi p,w,d;
    BinLift bl;
    void dfs (ll v){
        for (auto e: adjList[v]){
            if (e.F != p[v]){
                p[e.F] = v; w[e.F] = e.S; d[e.F] = d[v]+1; dfs(e.F);
            }
        }
    }
public:
    Solver(){
        cin >> n >> k;
        adjList.resize(n);
        q.resize(n+k-1);
        ll ctr = 0;
        for (auto &i: q){
            cin >> i.type;
            if (i.type == 'C') cin >> i.x;
            else{
                cin >> i.x >> i.y;
                i.x--; i.y--;
                if (i.type == 'S'){
                    adjList[i.x].emplace_back(i.y,ctr);
                    adjList[i.y].emplace_back(i.x,ctr);
                    ctr++;
                }
            }
        }
        p.assign(n,-1);
        w.assign(n,-1);
        d.assign(n,0);
        dfs(0);
        bl = BinLift(p,w,d);
    }
    void solve(){
        ll ctr = -1;
        for (auto &i: q){
            if (i.type == 'C') cout << "1\n";
            else if (i.type == 'S') ctr++;
            else{
                if (i.x == i.y){
                    cout << "yes\n";
                }else{
                    cout << ((bl.qry(i.x,i.y,ctr) ? "yes" : "no")) << "\n";
                }
            }
        }
    }
};

int main(){
    Solver mySolver;
    mySolver.solve();
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 74 ms 3532 KB Output is correct
2 Correct 102 ms 8096 KB Output is correct
3 Correct 85 ms 8128 KB Output is correct
4 Correct 111 ms 8196 KB Output is correct
5 Correct 128 ms 8332 KB Output is correct
6 Correct 90 ms 8288 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 74 ms 3532 KB Output is correct
2 Correct 102 ms 8096 KB Output is correct
3 Correct 85 ms 8128 KB Output is correct
4 Correct 111 ms 8196 KB Output is correct
5 Correct 128 ms 8332 KB Output is correct
6 Correct 90 ms 8288 KB Output is correct
7 Incorrect 65 ms 4300 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3428 KB Output is correct
2 Correct 299 ms 101860 KB Output is correct
3 Correct 286 ms 101736 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3428 KB Output is correct
2 Correct 299 ms 101860 KB Output is correct
3 Correct 286 ms 101736 KB Output is correct
4 Incorrect 64 ms 3560 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3476 KB Output is correct
2 Correct 290 ms 105720 KB Output is correct
3 Correct 296 ms 105744 KB Output is correct
4 Correct 323 ms 105172 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3476 KB Output is correct
2 Correct 290 ms 105720 KB Output is correct
3 Correct 296 ms 105744 KB Output is correct
4 Correct 323 ms 105172 KB Output is correct
5 Incorrect 82 ms 3384 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 3416 KB Output is correct
2 Correct 327 ms 105340 KB Output is correct
3 Correct 266 ms 105632 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 3416 KB Output is correct
2 Correct 327 ms 105340 KB Output is correct
3 Correct 266 ms 105632 KB Output is correct
4 Incorrect 66 ms 4344 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3452 KB Output is correct
2 Correct 254 ms 105728 KB Output is correct
3 Correct 314 ms 105756 KB Output is correct
4 Correct 300 ms 105124 KB Output is correct
5 Correct 67 ms 3460 KB Output is correct
6 Correct 319 ms 105404 KB Output is correct
7 Correct 253 ms 105596 KB Output is correct
8 Correct 404 ms 106492 KB Output is correct
9 Correct 326 ms 106400 KB Output is correct
10 Correct 332 ms 108592 KB Output is correct
11 Correct 413 ms 108216 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3452 KB Output is correct
2 Correct 254 ms 105728 KB Output is correct
3 Correct 314 ms 105756 KB Output is correct
4 Correct 300 ms 105124 KB Output is correct
5 Correct 67 ms 3460 KB Output is correct
6 Correct 319 ms 105404 KB Output is correct
7 Correct 253 ms 105596 KB Output is correct
8 Correct 404 ms 106492 KB Output is correct
9 Correct 326 ms 106400 KB Output is correct
10 Correct 332 ms 108592 KB Output is correct
11 Correct 413 ms 108216 KB Output is correct
12 Incorrect 72 ms 4308 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 3416 KB Output is correct
2 Correct 100 ms 8084 KB Output is correct
3 Correct 93 ms 8168 KB Output is correct
4 Correct 118 ms 8252 KB Output is correct
5 Correct 94 ms 8336 KB Output is correct
6 Correct 84 ms 8140 KB Output is correct
7 Correct 66 ms 4332 KB Output is correct
8 Correct 306 ms 104632 KB Output is correct
9 Correct 282 ms 104716 KB Output is correct
10 Correct 68 ms 4432 KB Output is correct
11 Correct 312 ms 109072 KB Output is correct
12 Correct 263 ms 109048 KB Output is correct
13 Correct 343 ms 108292 KB Output is correct
14 Correct 64 ms 4360 KB Output is correct
15 Correct 301 ms 105436 KB Output is correct
16 Correct 348 ms 105696 KB Output is correct
17 Correct 395 ms 106496 KB Output is correct
18 Correct 343 ms 106436 KB Output is correct
19 Correct 336 ms 108592 KB Output is correct
20 Correct 432 ms 108192 KB Output is correct
21 Correct 310 ms 104244 KB Output is correct
22 Correct 300 ms 104284 KB Output is correct
23 Correct 326 ms 105072 KB Output is correct
24 Correct 304 ms 105128 KB Output is correct
25 Correct 341 ms 105568 KB Output is correct
26 Correct 252 ms 104848 KB Output is correct
27 Correct 312 ms 104860 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 3416 KB Output is correct
2 Correct 100 ms 8084 KB Output is correct
3 Correct 93 ms 8168 KB Output is correct
4 Correct 118 ms 8252 KB Output is correct
5 Correct 94 ms 8336 KB Output is correct
6 Correct 84 ms 8140 KB Output is correct
7 Correct 66 ms 4332 KB Output is correct
8 Correct 306 ms 104632 KB Output is correct
9 Correct 282 ms 104716 KB Output is correct
10 Correct 68 ms 4432 KB Output is correct
11 Correct 312 ms 109072 KB Output is correct
12 Correct 263 ms 109048 KB Output is correct
13 Correct 343 ms 108292 KB Output is correct
14 Correct 64 ms 4360 KB Output is correct
15 Correct 301 ms 105436 KB Output is correct
16 Correct 348 ms 105696 KB Output is correct
17 Correct 395 ms 106496 KB Output is correct
18 Correct 343 ms 106436 KB Output is correct
19 Correct 336 ms 108592 KB Output is correct
20 Correct 432 ms 108192 KB Output is correct
21 Correct 310 ms 104244 KB Output is correct
22 Correct 300 ms 104284 KB Output is correct
23 Correct 326 ms 105072 KB Output is correct
24 Correct 304 ms 105128 KB Output is correct
25 Correct 341 ms 105568 KB Output is correct
26 Correct 252 ms 104848 KB Output is correct
27 Correct 312 ms 104860 KB Output is correct
28 Incorrect 63 ms 4376 KB Extra information in the output file
29 Halted 0 ms 0 KB -