Submission #863505

#	Time	Username	Problem	Language	Result	Execution time	Memory
863505		Cyber_Wolf	Inside information (BOI21_servers)	C++17	0 / 100	45 ms	7656 KiB

servers

#include <bits/stdc++.h>

using namespace std;

#define lg long long

const lg N = 2e5+5;

lg par[N], compSize[N];

lg get(lg src)
{
    if(src == par[src]) return src;
    return par[src] = get(par[src]);
}

void join(lg u, lg v)
{
    u = get(u), v = get(v);
    if(u == v)  return;
    if(compSize[u] > compSize[v])   swap(u, v);
    par[u] = v;
    compSize[v] += compSize[u];
    return;
}

int main()
{
    #ifdef CYBER
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    lg n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) par[i] = i, compSize[i] = 1;
    vector<array<lg, 3>> que;
    k += n-1;
    while(k--)
    {
        char c;
        cin >> c;
        if(c == 'S')
        {
            lg u, v;
            cin >> u >> v;
            que.push_back({c, u, v});
        }
        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});
        }
    }
    reverse(que.begin(), que.end());
    vector<lg> ans;
    for(auto [c, a, b] : que)
    {
        if(c == 'S')
        {
            join(a, b);
        }
        else if(c == 'Q')
        {
            ans.push_back(-2+(get(a) == get(b)));
        }
    }
    reverse(ans.begin(), ans.end());
    for(auto it : ans)
    {
        if(it < 0)
        {
            cout << (it == -2 ? "yes\n" : "no\n");
        }
        else{
            cout << it << '\n';
        }
    }
}

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5