Submission #863626

#	Time	Username	Problem	Language	Result	Execution time	Memory
863626		Cyber_Wolf	Inside information (BOI21_servers)	C++17	50 / 100	388 ms	115864 KiB

servers

#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
• 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