Submission #1224496

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

servers

//chcokolateman

#include<bits/stdc++.h> 

using namespace std;

int N,K,x[500005],y[500005],par[500005],w_par[500005],depth[500005],tin[500005],tout[500005],timer;
vector<pair<int,int>> adj[500005];
set<int> inside[500005];
char op[500005];

void dfs(int v,int p)
{
    tin[v] = ++timer;
    for(auto e : adj[v])
    {
        int u = e.first;
        int w = e.second;
        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 l_w = K+1;
    int max_edge = 0;
    while(!is_ancesstor(a,b))
    {
        ret &= (w_par[a] <= l_w);
        max_edge = max(max_edge,w_par[a]);
        l_w = w_par[a];
        a = par[a];
    }
    int r_w = 0;
    while(b != a)
    {
        ret &= (w_par[b] >= r_w);
        max_edge = max(max_edge,w_par[b]);
        r_w = w_par[b];
        b = par[b];
    }
    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);
    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
        {
            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:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d%d",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~
servers.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf(" %c%d",&op[i],&x[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
servers.cpp:67:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |             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