oj.uz

Submission #863626

# Submission time Handle Problem Language Result Execution time Memory
863626 2023-10-20T16:00:38 Z Cyber_Wolf Inside information (BOI21_servers) C++17
50 / 100
 388 ms 115864 KB 
#include <bits/stdc++.h>

using namespace std;

#define lg long long
#define mid (lr+hr)/2

const lg N = 2e5+5;

vector<array<lg, 2>> adj[N];
lg anc[N][20], inc[N][20], mxm[N][20], depth[N], decr[N][20];
// lg head[N], in[N], out[N], tmp, sz[N], p[N], euler[N], co[N], loc[N], depth[N];
// struct Node{
//     lg f;
//     lg l;
//     lg sz;
//     lg mnm;
//     bool inc;
//     bool dec;
//     Node()
//     {
//         sz = 1;
//         f = l = 0;
//         inc = dec = 0;
//         mnm = 0;
//     }
// } seg[N << 2];
// //cost, first, last, increase, decrease

// Node fake()
// {
//     Node e;
//     e.f = -1;
//     return e;
// }

// Node merge(Node a, Node b)
// {
//     if(a.f == -1)   return b;
//     if(b.f == -1)   return a;
//     Node c;
//     c.f = a.f;
//     c.l = b.l;
//     c.sz = a.sz+b.sz;
//     c.inc = (a.inc && b.inc && (a.l < b.f || a.l == -2 || b.f == -2));
//     c.dec = (a.dec && b.dec && (a.l > b.f || a.l == -2 || b.f == -2));
//     c.mnm = min(a.mnm, b.mnm);
//     if(c.mnm == -2 && c.f != -2)    c.inc = c.dec = 0;
//     if(b.f == -2)   c.inc = c.dec = 0;
//     return c;
// }

// void build(lg node, lg lr, lg hr)
// {
//     if(lr == hr)    
//     {
//         seg[node].inc = seg[node].dec = 1;
//         seg[node].l = seg[node].f = -2;
//         seg[node].sz = 1;
//         seg[node].mnm = seg[node].l;
//         return;
//     }
//     build(node << 1, lr, mid);
//     build(node << 1 | 1, mid+1, hr);
//     seg[node] = merge(seg[node << 1], seg[node << 1 | 1]);
//     return;
// }

// void update(lg node, lg lr, lg hr, lg idx, lg val)
// {
//     if(lr > idx || hr < idx)    return ;
//     if(lr == hr)
//     {
//         seg[node].f = seg[node].l = val;
//         seg[node].mnm = seg[node].l;
//         return ;
//     }
//     update(node << 1, lr, mid, idx, val);
//     update(node << 1 | 1, mid+1, hr, idx, val);
//     seg[node] = merge(seg[node << 1], seg[node << 1 | 1]);
//     return;
// }

// Node get(lg node, lg lr, lg hr, lg lq, lg hq)
// {
//     if(lq > hr || lr > hq)  return fake();
//     if(lq <= lr && hr <= hq)    return seg[node];
//     return merge(get(node << 1, lr, mid, lq, hq), get(node << 1 | 1, mid+1, hr, lq, hq));
// }

// void dfs(lg src, lg par = -1)
// {
//     sz[src] = 1;
//     for(auto [it, c] : adj[src])
//     {
//         if(it == par)   continue;
//         depth[it] = depth[src]+1;
//         p[it] = src;
//         co[it] = c;
//         dfs(it, src);
//         sz[src] += sz[it];
//     }
//     return ;
// }

// void dfs2(lg src, lg par = -1)
// {
//     in[src] = ++tmp;
//     euler[tmp] = src;
//     loc[src] = tmp;
//     if(p[src] == adj[src][0][0])    reverse(adj[src].begin(), adj[src].end());
//     for(auto &it : adj[src])
//     {
//         if(it[0] == par)   
//         {
//             continue;
//         }
//         if(sz[it[0]] > sz[adj[src][0][0]]) swap(adj[src][0], it);
//     }
//     for(auto [it, c] : adj[src])
//     {
//         if(it == par)
//         {
//             continue;
//         }
//         head[it] = (it == adj[src][0][0] ? head[src] : it);
//         dfs2(it, src);
//     }
//     out[src] = tmp;
// }

// lg lca(lg a, lg b)
// {
//     while(head[a] != head[b])
//     {
//         if(depth[head[b]] > depth[head[a]]) swap(a, b);
//         a = p[head[a]];
//     }
//     if(depth[b] > depth[a]) swap(a, b);
//     return b;
// }


void dfs(lg src, lg par = -1)
{
    for(auto [it, c] : adj[src])
    {
        if(it == par)   continue;
        anc[it][0] = src;
        depth[it] = depth[src]+1;
        mxm[it][0] = c;
        inc[it][0] = (mxm[src][0] < c);
        decr[it][0] = (mxm[src][0] > c);
        for(int i = 1; i < 20; i++)
        {
            anc[it][i] = anc[anc[it][i-1]][i-1];
            inc[it][i] = (inc[anc[it][i-1]][i-1] && inc[it][i-1]);
            decr[it][i] = (decr[anc[it][i-1]][i-1] && decr[it][i-1]);
            mxm[it][i] = max(mxm[anc[it][i-1]][i-1], mxm[it][i-1]);
        }
        dfs(it, src);
    }
    return;
}

lg lca(lg a, lg b)
{
    if(depth[a] < depth[b]) swap(a, b);
    lg diff = (depth[a]-depth[b]);
    for(int i = 0; i < 20; i++)
    {
        if((1ll << i)&diff)
        {
            a = anc[a][i];
        }
    }
    if(a == b)  return a;
    for(int i = 19; i >= 0; i--)
    {
        if(anc[a][i] == anc[b][i])  continue;
        a = anc[a][i];
        b = anc[b][i];
    }
    return anc[a][0];
}

int main()
{
    #ifdef CYBER
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    lg n, k;
    cin >> n >> k;
    vector<array<lg, 3>> que;
    lg id = 1;
    k += n-1;
    while(k--)
    {
        char c;
        cin >> c;
        if(c == 'S')
        {
            lg u, v;
            cin >> u >> v;
            que.push_back({c, u, v});
            adj[u].push_back({v, id});
            adj[v].push_back({u, id});
            id++;
        }
        else if(c == 'Q')
        {
            lg u, v;
            cin >> u >> v;
            que.push_back({c, u, v});
        }
        else{
            lg u;
            cin >> u;
            que.push_back({c, u, 0});
        }
    }
    dfs(1);
    lg ava = 0;
    for(auto [c, a, b] : que)
    {
        if(c == 'S')
        {
            ava++;
        }
        else if(c == 'Q')
        {
            lg _lca = lca(a, b);
            lg diff = depth[b]-depth[_lca];
            lg d = a, e = b;
            lg mx = 0, in = 1, de = 1;
            for(int i = 0; i < 20 && diff > 0; i++)
            {
                if((1ll << i)&diff)
                {
                    mx = max(mx, mxm[b][i]);
                    b = anc[b][i];
                }
            }
            diff = depth[a]-depth[_lca];
            for(int i = 0; i < 20 && diff > 0; i++)
            {
                if((1ll << i)&diff)
                {
                    mx = max(mx, mxm[a][i]);
                    a = anc[a][i];
                }
            }
            a = d, b = e;
            diff = depth[b]-depth[_lca]-1;
            for(int i = 0; i < 20 && diff > 0; i++)
            {
                if((1ll << i)&diff)
                {
                    de &= decr[b][i];
                    b = anc[b][i];
                }
            }
            diff = depth[a]-depth[_lca]-1;
            for(int i = 0; i < 20 && diff > 0; i++)
            {
                if((1ll << i)&diff)
                {
                    in &= inc[a][i];
                    a = anc[a][i];
                }
            }
            // cout << de << ' ' << in << ' ' << mx << '\n';
            // cout << a << ' ' << b << ' ' << _lca << '\n';
            if(a != b && depth[a] == depth[b])    de &= (mxm[a][0] > mxm[b][0]);
            // cout << de << ' ' << in << ' ' << mx << '\n';
            cout << (de && in && mx <= ava ? "yes\n" : "no\n");
            // swap(a, b);
            // lg _lca = lca(a, b);
            // lg cur = 1;
            // lg la = 1e18;
            // Node o;
            // while(head[b] != head[_lca] && cur)
            // {
            //     o = get(1, 1, n, loc[head[b]], loc[b]);
            //     // cout << b << ' ';
            //     cur &= (o.l < la);
            //     la = o.f;
            //     cur &= o.inc;
            //     cur &= (o.mnm > -2);
            //     // cout << "MNM: " << o.mnm << '\n';
            //     b = p[head[b]];
            // }
            // // cout << b << ' ' << _lca << '\n';
            // // cout << "DEC " << cur << ' ';
            // o = get(1, 1, n, loc[_lca], loc[b]);
            // cur &= o.inc;
            // // cout << "DEC " << cur << ' ';
            // if(_lca != b)   cur &= (o.l < la);
            // // cout << "DEC " << cur << ' ';
            // la = -1e18;
            // while(head[a] != head[_lca] && cur)
            // {
            //     o = get(1, 1, n, loc[head[a]], loc[a]);
            //     // cout << a << ' ';
            //     cur &= (o.l > la);
            //     la = o.f;
            //     cur &= o.dec;
            //     cur &= (o.mnm > -2);
            //     // cout << "MNM: " << o.mnm << '\n';
            //     a = p[head[a]];
            // }
            // // cout << a << ' ' << _lca << '\n';
            // o = get(1, 1, n, loc[_lca], loc[a]);
            // // cout << "DEC " << cur << ' ';
            // cur &= o.dec;
            // // cout << "DEC " << cur << ' ';
            // if(_lca != a)   cur &= (o.l > la);
            // // cout << "DEC " << cur << ' ';
            // cout << (cur ? "yes\n" : "no\n");
        }
        // for(int i = 1; i <= n; i++)
        // {
        //     lg x = get(1, 1, n, i, i).f;
        //     if(x > 1e15)    cout << "inf ";
        //     else    cout << x << ' ';
        // }
        // cout << '\n';
    }
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 13852 KB Output is correct
2 Correct 93 ms 18528 KB Output is correct
3 Correct 71 ms 18708 KB Output is correct
4 Correct 94 ms 18628 KB Output is correct
5 Correct 86 ms 18936 KB Output is correct
6 Correct 78 ms 18452 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 13852 KB Output is correct
2 Correct 93 ms 18528 KB Output is correct
3 Correct 71 ms 18708 KB Output is correct
4 Correct 94 ms 18628 KB Output is correct
5 Correct 86 ms 18936 KB Output is correct
6 Correct 78 ms 18452 KB Output is correct
7 Incorrect 62 ms 14012 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 57 ms 14012 KB Output is correct
2 Correct 223 ms 100076 KB Output is correct
3 Correct 197 ms 100600 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 14012 KB Output is correct
2 Correct 223 ms 100076 KB Output is correct
3 Correct 197 ms 100600 KB Output is correct
4 Incorrect 57 ms 14016 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 51 ms 14020 KB Output is correct
2 Correct 242 ms 115372 KB Output is correct
3 Correct 251 ms 115700 KB Output is correct
4 Correct 278 ms 115188 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 14020 KB Output is correct
2 Correct 242 ms 115372 KB Output is correct
3 Correct 251 ms 115700 KB Output is correct
4 Correct 278 ms 115188 KB Output is correct
5 Incorrect 49 ms 13856 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 59 ms 13940 KB Output is correct
2 Correct 256 ms 102992 KB Output is correct
3 Correct 208 ms 102928 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 13940 KB Output is correct
2 Correct 256 ms 102992 KB Output is correct
3 Correct 208 ms 102928 KB Output is correct
4 Incorrect 57 ms 14008 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 61 ms 14172 KB Output is correct
2 Correct 250 ms 115444 KB Output is correct
3 Correct 249 ms 115408 KB Output is correct
4 Correct 271 ms 114608 KB Output is correct
5 Correct 59 ms 13988 KB Output is correct
6 Correct 245 ms 102584 KB Output is correct
7 Correct 210 ms 102980 KB Output is correct
8 Correct 332 ms 102392 KB Output is correct
9 Correct 241 ms 102640 KB Output is correct
10 Correct 244 ms 109248 KB Output is correct
11 Correct 356 ms 106764 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 14172 KB Output is correct
2 Correct 250 ms 115444 KB Output is correct
3 Correct 249 ms 115408 KB Output is correct
4 Correct 271 ms 114608 KB Output is correct
5 Correct 59 ms 13988 KB Output is correct
6 Correct 245 ms 102584 KB Output is correct
7 Correct 210 ms 102980 KB Output is correct
8 Correct 332 ms 102392 KB Output is correct
9 Correct 241 ms 102640 KB Output is correct
10 Correct 244 ms 109248 KB Output is correct
11 Correct 356 ms 106764 KB Output is correct
12 Incorrect 48 ms 14012 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 65 ms 14016 KB Output is correct
2 Correct 83 ms 18376 KB Output is correct
3 Correct 83 ms 18588 KB Output is correct
4 Correct 102 ms 18792 KB Output is correct
5 Correct 81 ms 18948 KB Output is correct
6 Correct 71 ms 18644 KB Output is correct
7 Correct 55 ms 14008 KB Output is correct
8 Correct 213 ms 100140 KB Output is correct
9 Correct 197 ms 100340 KB Output is correct
10 Correct 49 ms 13984 KB Output is correct
11 Correct 250 ms 115864 KB Output is correct
12 Correct 237 ms 115448 KB Output is correct
13 Correct 277 ms 114536 KB Output is correct
14 Correct 65 ms 14152 KB Output is correct
15 Correct 250 ms 102812 KB Output is correct
16 Correct 217 ms 103152 KB Output is correct
17 Correct 305 ms 102424 KB Output is correct
18 Correct 274 ms 102488 KB Output is correct
19 Correct 255 ms 109624 KB Output is correct
20 Correct 388 ms 107004 KB Output is correct
21 Correct 249 ms 100208 KB Output is correct
22 Correct 215 ms 101016 KB Output is correct
23 Correct 258 ms 102448 KB Output is correct
24 Correct 230 ms 101156 KB Output is correct
25 Correct 262 ms 104176 KB Output is correct
26 Correct 198 ms 101116 KB Output is correct
27 Correct 201 ms 100676 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 14016 KB Output is correct
2 Correct 83 ms 18376 KB Output is correct
3 Correct 83 ms 18588 KB Output is correct
4 Correct 102 ms 18792 KB Output is correct
5 Correct 81 ms 18948 KB Output is correct
6 Correct 71 ms 18644 KB Output is correct
7 Correct 55 ms 14008 KB Output is correct
8 Correct 213 ms 100140 KB Output is correct
9 Correct 197 ms 100340 KB Output is correct
10 Correct 49 ms 13984 KB Output is correct
11 Correct 250 ms 115864 KB Output is correct
12 Correct 237 ms 115448 KB Output is correct
13 Correct 277 ms 114536 KB Output is correct
14 Correct 65 ms 14152 KB Output is correct
15 Correct 250 ms 102812 KB Output is correct
16 Correct 217 ms 103152 KB Output is correct
17 Correct 305 ms 102424 KB Output is correct
18 Correct 274 ms 102488 KB Output is correct
19 Correct 255 ms 109624 KB Output is correct
20 Correct 388 ms 107004 KB Output is correct
21 Correct 249 ms 100208 KB Output is correct
22 Correct 215 ms 101016 KB Output is correct
23 Correct 258 ms 102448 KB Output is correct
24 Correct 230 ms 101156 KB Output is correct
25 Correct 262 ms 104176 KB Output is correct
26 Correct 198 ms 101116 KB Output is correct
27 Correct 201 ms 100676 KB Output is correct
28 Incorrect 58 ms 14008 KB Extra information in the output file
29 Halted 0 ms 0 KB -