제출 #899151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899151		Nahian9696	Inside information (BOI21_servers)	C++17	5 / 100	74 ms	6492 KiB

servers

#include <bits/stdc++.h>

using namespace std;

typedef long double                         ld;
typedef long long                           lli;
typedef vector<int32_t>                     vi;
typedef vector<ld>                          vld;
typedef vector<lli>                         vlli;
typedef pair<lli, lli>                      pii;


#define int                                 int64_t
#define endl                                "\n"
#define inp(n)                              lli n; cin >> n
#define inpstr(s)                           string s; cin >> s
#define inp2(a,b)                           lli a,b; cin >> a >> b
#define inparr(arr,n)                       lli arr[n]; f0(t_ind, n) cin >> arr[t_ind]
#define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
#define f1(i,n)                             for(int32_t i = 1; i <= (n); i++)

#define testIn                              cin >> test
#define tests                               for(int32_t testNo=1; testNo <= (test); testNo++)

#define all(x)                              (x).begin(), (x).end()
#define rall(x)                             (x).rbegin(), (x).rend()
#define len(a)                              ((int64_t)(a).size())
#define lcm(a, b)                           (((a)*(b))/gcd(a,b))
#define ff                                  first
#define ss                                  second

#define Yes                                 cout << "Yes" << endl
#define No                                  cout << "No" << endl
#define YES                                 cout << "YES" << endl
#define NO                                  cout << "NO" << endl
#define finish                              return 0
#define clean                               fflush(stdout)

#define Inf                                 (lli)(1e9)
#define Eps                                 (ld)(1e-9)
#define PI                                  (ld)(3.141592653589793238462643383279502884197169L)
#define MOD                                 (int32_t)(1e9+7)


template<typename dataType1>
inline void print(dataType1 a) {cout << a << endl;}
template<typename dataType1, typename dataType2>
inline void print(dataType1 a, dataType2 b) {cout << a << " " << b << endl;}
template<typename dataType1, typename dataType2, typename dataType3>
inline void print(dataType1 a, dataType2 b, dataType3 c) {cout << a << " " << b << " " << c << endl;}
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
inline void print(dataType1 a, dataType2 b, dataType3 c, dataType4 d) {cout << a << " " << b << " " << c << " " << d << endl;}
template<typename dataType>
inline dataType abs(dataType k) {if (k >= 0) return k; else return (-k);}
template<typename dataType>
inline bool isEqual(dataType a, dataType b) {return (abs((dataType)(a-b)) < 1e-9);}






// Solver functions

int32_t solve1(int32_t);


int32_t solve2(int32_t);


int32_t solve3(int32_t);


int32_t main() {

    #if defined __has_include
        #if __has_include("LOCAL.hh")
            #include "LOCAL.hh"
        #endif
    #endif

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
        using namespace std::chrono;
        cout << fixed << setprecision(9);
        auto begin = steady_clock::now();
    #else
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif

    // Previous code



    // Main code
    int32_t test = 1;

    // testIn;

    tests {

        solve1(testNo);

    }
    #ifdef LOCAL
        auto end = steady_clock::now();
        cout << "\nTime : " 
             << (ld)duration_cast<nanoseconds>
                (end - begin).count()/1000000000 
             << "s" << endl;
    #endif
    finish;
}

    int left_par[120005], right_par[120005];
    int lval[120005], rval[120005];

int lpar(int x) {
    if(left_par[x] == x) return x;
    left_par[x] = lpar(left_par[x]);
    return left_par[x];
}

int rpar(int x) {
    if(right_par[x] == x) return x;
    right_par[x] = lpar(right_par[x]);
    return right_par[x];
}



int32_t solve1(int32_t testNo) {
    // cout << "Case #" << testNo << ": ";
    // cout << endl;
    
    inp2(n, k);

    if(false) {

    int share_degree[n+1] = {0};

    set<int> has_set[n+1];

    f1(i, n) has_set[i].insert(i);

    f0(i, n+k-1) {
        char ch;
        cin >> ch;
        if(ch == 'S') {
            inp2(a, b);

            for(int x: has_set[b]) share_degree[x]++;
            for(int x: has_set[a]) share_degree[x]++;

            for(int x: has_set[b]) has_set[a].insert(x);
            for(int x: has_set[a]) has_set[b].insert(x);
        } else if(ch == 'Q') {
            inp2(a,d);
            if(a == d) print("yes");
            else if(has_set[a].find(d) != has_set[a].end()) print("yes");
            else print("no");
        } else {
            inp(a);
            // print(has_set[a].size());
            print(share_degree[a]+1);
        }
    }
    } else {
    
    int left[n+1] = {0};
    int right[n+1] = {0};
    


    f1(i, n) left[i] = 1, right[i] = 1, left_par[i] = i, right_par[i] = i, lval[i] = i, rval[i] = i;

    // set<int> has_set[n+1];

    // f1(i, n) has_set[i].insert(i);


    f0(i, n+k-1) {
        char ch;
        cin >> ch;
        if(ch == 'S') {
            inp2(a, b);

            if(a > b) swap(a,b);
            
            right[a] += right[b];
            left[b] += left[a];


            left_par[b] = lpar(a);
            right_par[a] = rpar(b);

            lval[left_par[b]] = b;
            rval[right_par[a]] = a;

        } else if(ch == 'Q') {
            inp2(a, d);
            if( a < d ) {
                if(d < a + right[a]) print("yes");
                else print("no");
            } else if( a > d ) {
                if(d > a - left[a]) print("yes");
                else print("no");
            } else print("yes");
        } else {
            inp(a);
            // print(has_set[a].size());
            int ll = lval[lpar(a)], rr = rval[rpar(a)];
            print(abs(ll - rr) +1);
        }
    }
    }







    finish;
}



int32_t solve2(int32_t testNo) {
    // cout << "Case #" << testNo << ": ";
    // cout << endl;

    finish;
}



int32_t solve3(int32_t testNo) {
    // cout << "Case #" << testNo << ": ";
    // cout << endl;
    
    finish;
}

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 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