Submission #398563

#	Time	Username	Problem	Language	Result	Execution time	Memory
398563		N_o_o_B	Inside information (BOI21_servers)	C++14	0 / 100	35 ms	1552 KiB

servers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<pll> vll;
typedef vector<vl> vvl;

#define fori(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i >= 0; i--)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repd(i, a, b) for (int i = a; i >= b; i--)
#define trav(x, a) for (auto &x : a)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define sz(a) (int)(a).size()
#define fi first
#define se second

clock_t time_p = clock();
void time_taken()
{
    time_p = clock() - time_p;
    cerr << "Time Taken : " << (float)(time_p) / CLOCKS_PER_SEC << "\n";
}

const ll mod = 1e9 + 7;
const ll INF = 1e18;

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vi par(n, -1);

    function<int(int)> get = [&](int x) -> int {
        return (par[x] < 0 ? x : par[x] = get(par[x]));
    };

    function<bool(int, int)> merge = [&](int x, int y) -> bool {
        x = get(x), y = get(y);
        if (x == y)
            return 0;
        if (par[x] > par[y])
            swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return 1;
    };

    fori(_, n - 1 + q)
    {
        char t;
        cin >> t;
        if (t == 'S')
        {
            int x, y;
            cin >> x >> y, --x, --y;
            assert(merge(x, y));
        }
        else if (t == 'Q')
        {
            int a, d;
            cin >> a >> d, --a, --d;
            if (get(a) == get(d))
            {
                cout << "yes" << endl;
            }
            else
            {
                cout << "no" << endl;
            }
        }
        else
        {
            assert(t == 'C');
            int d;
            cin >> d, --d;
            cout << -par[get(d)] << endl;
        }
    }

    time_taken();
    return 0;
}

• 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