Submission #1224625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224625		KALARRY	Inside information (BOI21_servers)	C++20	48 / 100	175 ms	69168 KiB

servers

//chcokolateman

#include<bits/stdc++.h> 

using namespace std;

int N,K,x[500005],y[500005],par[120005],w_par[120005],tin[120005],tout[120005],timer,up[120005][20],up_max[120005][20],up_min[120005][20],opened[120005];
bool is_inc[120005][20],is_deac[120005][20];
vector<pair<int,int>> adj[120005];
set<int> inside[120005];
char op[500005];

void dfs(int v,int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    up_max[v][0] = up_min[v][0] = w_par[v];
    is_inc[v][0] = is_deac[v][0] = true;
    for(int L = 1 ; L <= 18 ; L++)
    {
        up[v][L] = up[up[v][L-1]][L-1];
        up_max[v][L] = max(up_max[v][L-1],up_max[up[v][L-1]][L-1]);
        up_min[v][L] = min(up_min[v][L-1],up_min[up[v][L-1]][L-1]);
        is_inc[v][L] = (is_inc[v][L-1] && is_inc[up[v][L-1]][L-1]) && (up[v][L-1]==1 || w_par[up[v][L-1]] > up_max[v][L-1]);
        is_deac[v][L] = (is_deac[v][L-1] && is_deac[up[v][L-1]][L-1]) && (up[v][L-1]==1 || w_par[up[v][L-1]] < up_min[v][L-1]);
    }
    for(auto e : adj[v])
    {
        int u = e.first;
        int w = e.second;
        // printf("%d %d %d\n",v,u,w);
        if(u != p)
        {
            par[u] = v;
            w_par[u] = w;
            dfs(u,v);
        }
    }
    tout[v] = ++timer;
}

bool is_ancesstor(int a,int b)
{
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

bool conected(int a,int b,int t)
{
    int l = a;
    bool ret = true;
    int max_edge = 0;
    int l_w = 1e9;
    for(int L = 18 ; L >= 0 ; L--)
    {
        while(!is_ancesstor(up[a][L],b))
        {
            // printf("IN %d %d %d\n",a,b,L);
            ret &= (is_deac[a][L] && l_w > w_par[a]);
            // if(ret == false)
            //     printf("Fucked at %d\n\n",L);
            max_edge = max(max_edge,up_max[a][L]);
            l_w = up_min[a][L];
            a = up[a][L];
        }
    }
    if(!is_ancesstor(a,b))
    {
        ret &= (l_w > w_par[a]);
        max_edge = max(max_edge,w_par[a]);
        l_w = w_par[a];
        a = par[a];
    }
    int r_w = 0;
    for(int L = 18 ; L >= 0 ; L--)
    {
        while(!is_ancesstor(up[b][L],a))
        {
            ret &= (is_inc[b][L] && r_w < w_par[b]);
            max_edge = max(max_edge,up_max[b][L]);
            r_w = up_max[b][L];
            b = up[b][L];
        }
    }
    if(a != b)
    {
        ret &= (r_w < w_par[b]);
        max_edge = max(max_edge,w_par[b]);
        r_w = w_par[b];
        b = par[a];
    }
    ret &= (l_w >= r_w);
    return ret && max_edge <= t;
}

int main()
{
    scanf("%d%d",&N,&K);
    K += N-1;
    for(int i = 1 ; i <= K ; i++)
    {
        scanf(" %c%d",&op[i],&x[i]);
        if(op[i] != 'C')
            scanf("%d",&y[i]);
        if(op[i]=='S')
        {
            adj[x[i]].push_back({y[i],i});
            adj[y[i]].push_back({x[i],i});
        }
    }
    par[1] = 1;
    dfs(1,1);
    for(int i = 1 ; i <= N ; i++)
        inside[i].insert(i);
    int operations = 0;
    for(int a,b,i = 1 ; i <= K ; i++)
    {
        a = x[i];
        b = y[i];
        if(op[i] == 'Q')
        {
            if(conected(a,b,i))
                printf("yes\n");
            else
                printf("no\n");
        }
        else if(op[i] == 'C')
        {
            int counter = 0;
            if(!opened[a])
                counter = 1;
            else
                counter = 1 + operations - opened[a] + 1;
            printf("%d\n",counter);
        }
        else
        {
            opened[max(a,b)] = ++operations;
        }
    }
    return 0;
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     scanf("%d%d",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~
servers.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         scanf(" %c%d",&op[i],&x[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
servers.cpp:103:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |             scanf("%d",&y[i]);
      |             ~~~~~^~~~~~~~~~~~

• Subtask 1-1: 2 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 2 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 5 / 5
• Subtask 3-2: 0 / 5
• Subtask 4-1: 10 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 12 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 17 / 17
• Subtask 6-2: 0 / 18