Submission #863479

#	Time	Username	Problem	Language	Result	Execution time	Memory
863479		Cyber_Wolf	Inside information (BOI21_servers)	C++17	5 / 100	1085 ms	524288 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;
    set<lg> se[n];
    vector<lg> dat(n);
    for(int i = 0; i < n; i++)  se[i].insert(i), dat[i] = 1;
    k += n-1;
    while(k--)
    {
        char c;
        cin >> c;
        if(c == 'S')
        {
            lg u, v;
            cin >> u >> v;
            u--, v--;
            if(se[v].size() > se[u].size()) swap(u, v);
            for(auto it : se[u])
            {
                dat[it]++;
            }
            for(auto it : se[v])
            {
                se[u].insert(it);
                dat[it]++;
            }
            se[v] = se[u];
        }
        else if(c == 'Q')
        {
            lg u, v;
            cin >> u >> v;
            u--, v--;
            cout << ((se[u].find(v) != se[u].end()) ? "yes\n" : "no\n");
        }
        else{
            lg u;
            cin >> u;
            u--;
            cout << dat[u] << '\n';
        }
    }
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 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