Submission #1224645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224645		KALARRY	Inside information (BOI21_servers)	C++20	2 / 100	3588 ms	589824 KiB

servers

//chcokolateman

#include<bits/stdc++.h> 

using namespace std;
//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],l[120005],r[120005],inc_l[120005],inc_r[120005],s[120005],p[120005],maxim[120005],minim[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 find_Sett(int i)
{
    if(p[i]==i)
        return i;
    p[i] = find_Sett(p[i]);
    return p[i];
}

bool is_Same_Sett(int i,int j)
{
    return find_Sett(i)==find_Sett(j);
}

int find_minim(int i)
{
    return minim[find_Sett(i)];
}

int find_maxim(int i)
{
    return maxim[find_Sett(i)];
}

void union_Sett(int i,int j)
{
    if(is_Same_Sett(i,j))
        return;
    int x = find_Sett(i);
    int y = find_Sett(j);
    if(s[x] > s[y])
    {
        p[y] = x;
        s[x] += s[y];
        maxim[x] = max(maxim[x],maxim[y]);
        minim[x] = min(minim[x],minim[y]);
    }
    else
    {
        p[x] = y;
        s[y] += s[x];
        maxim[y] = max(maxim[x],maxim[y]);
        minim[y] = min(minim[x],minim[y]);
    }
}



int main()
{
    scanf("%d%d",&N,&K);
    for(int i = 1 ; i <= N ; i++)
    {
        p[i] = i;
        s[i] = i;
        minim[i] = i;
        maxim[i] = i;
    }
    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')
        {
            l[max(x[i],y[i])] = i;
            r[min(x[i],y[i])] = i;
            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);
    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;
            for(int j = 1 ; j <= N ; j++)
                if(inside[j].count(a))
                    counter++;
            printf("%d\n",counter);
        }
        else
        {
            union_Sett(a,b);
            for(auto k : inside[a])
                inside[b].insert(k);
            for(auto k: inside[b])
                inside[a].insert(k);
        }
    }
    return 0;
}

Compilation message (stderr)

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

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