oj.uz

Submission #899148

# Submission time Handle Problem Language Result Execution time Memory
899148 2024-01-05T14:12:10 Z Nahian9696 Inside information (BOI21_servers) C++17
10 / 100
 1999 ms 378320 KB 
#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);}



bool isPrefix(string &s, string &y) {
    if(s.length() > y.length()) return false;
    f0(i, s.length()) if(s[i] != y[i]) return false;
    return true;
}
bool ispalindrom(string s) {
    f0(i, s.length()/2) if(s[i] != s[s.length()-i-1]) return false;
    return true;
}


template<typename dataType1, typename dataType2>
void allPrimeVector(dataType1 n, dataType2 &primeList) {
    bool prime[n+1];
    memset(prime, true, sizeof(prime));

    for (int32_t p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (dataType1 i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }

    for (int32_t p = 2; p <= n; p++)
        if (prime[p])
            primeList.pb(p);
}

template<typename dataType>
string decimalTokbitsBinary(dataType n,dataType k) {
    string s = bitset<64>(n).to_string();

    return s.substr(64-k);
}


template<typename dataType>
dataType val(char c) {
    if (c >= '0' && c <= '9')
        return (dataType)c - '0';
    else
        return (dataType)c - 'A' + 10;
}
template<typename dataType>
dataType nthBaseToDecimal(string str, dataType base) {
    int32_t len = str.length();
    int32_t power = 1;
    dataType num = 0;
 
    for (int32_t i = len - 1; i >= 0; i--) {
        num += (val<dataType>(str[i]) * power);
        power *= base;
    }

    return num;
}

template<typename dataType>
char reVal(dataType num) {
    if (num >= 0 && num <= 9)
        return (char)(num + '0');
    else
        return (char)(num - 10 + 'A');
}
template<typename dataType>
string nthBasefromDeci(dataType inputNum, dataType base) {
    string res = "";
    while (inputNum > 0) {
        res += reVal(inputNum % base);
        inputNum /= base;
    }
    if (res == "")
        res = "0";
    return string(rall(res));
}

template<typename dataType>
dataType phi(dataType n) {
    dataType result = n;
    for(int32_t p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}
template<typename dataType1, typename dataType2, typename dataType3>
int64_t powMod(dataType1 base, dataType2 n, dataType3 mod) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        int64_t t_pow = (int64_t)powMod(base, n/2, mod);
        return ((t_pow*t_pow) % mod);
    }
    int64_t t_pow = (int64_t)powMod(base, (n-1)/2, mod);
    return ((int64_t)base * ((t_pow*t_pow) % mod) % mod);
}
template<typename dataType1, typename dataType2>
int64_t modInverse(dataType1 n, dataType2 mod, bool isPrime = true) {
    if(isPrime) return powMod(n, mod-2, mod);
    return powMod(n, phi(mod)-1, mod);
}
template<typename dataType1, typename dataType2, typename dataType3>
int64_t modDivide(dataType1 a, dataType2 b, dataType3 mod, bool isPrime = true) {
    return (((int64_t)a * modInverse(b, mod, isPrime)) % mod);
}


// 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(n <= 4000) {

    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;
}

Compilation message

servers.cpp: In function 'bool isPrefix(std::string&, std::string&)':
servers.cpp:19:66: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
      |                                                                  ^
servers.cpp:62:5: note: in expansion of macro 'f0'
   62 |     f0(i, s.length()) if(s[i] != y[i]) return false;
      |     ^~
servers.cpp: In function 'bool ispalindrom(std::string)':
servers.cpp:19:66: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
      |                                                                  ^
servers.cpp:66:5: note: in expansion of macro 'f0'
   66 |     f0(i, s.length()/2) if(s[i] != s[s.length()-i-1]) return false;
      |     ^~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 860 KB Output is correct
2 Correct 27 ms 2140 KB Output is correct
3 Correct 226 ms 47812 KB Output is correct
4 Correct 26 ms 2008 KB Output is correct
5 Correct 25 ms 1884 KB Output is correct
6 Correct 1730 ms 377408 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 860 KB Output is correct
2 Correct 27 ms 2140 KB Output is correct
3 Correct 226 ms 47812 KB Output is correct
4 Correct 26 ms 2008 KB Output is correct
5 Correct 25 ms 1884 KB Output is correct
6 Correct 1730 ms 377408 KB Output is correct
7 Correct 20 ms 1772 KB Output is correct
8 Correct 25 ms 3000 KB Output is correct
9 Correct 260 ms 60816 KB Output is correct
10 Correct 24 ms 2908 KB Output is correct
11 Correct 22 ms 2396 KB Output is correct
12 Correct 1777 ms 377852 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1620 KB Output is correct
2 Incorrect 54 ms 8160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1620 KB Output is correct
2 Incorrect 54 ms 8160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1368 KB Output is correct
2 Correct 46 ms 8280 KB Output is correct
3 Correct 45 ms 8276 KB Output is correct
4 Correct 54 ms 8096 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1368 KB Output is correct
2 Correct 46 ms 8280 KB Output is correct
3 Correct 45 ms 8276 KB Output is correct
4 Correct 54 ms 8096 KB Output is correct
5 Correct 18 ms 1372 KB Output is correct
6 Incorrect 45 ms 8180 KB Extra information in the output file
7 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1584 KB Output is correct
2 Incorrect 52 ms 8020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1584 KB Output is correct
2 Incorrect 52 ms 8020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1372 KB Output is correct
2 Correct 47 ms 8300 KB Output is correct
3 Correct 49 ms 8112 KB Output is correct
4 Correct 40 ms 8264 KB Output is correct
5 Correct 18 ms 1372 KB Output is correct
6 Incorrect 43 ms 8144 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1372 KB Output is correct
2 Correct 47 ms 8300 KB Output is correct
3 Correct 49 ms 8112 KB Output is correct
4 Correct 40 ms 8264 KB Output is correct
5 Correct 18 ms 1372 KB Output is correct
6 Incorrect 43 ms 8144 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1512 KB Output is correct
2 Correct 28 ms 3160 KB Output is correct
3 Correct 234 ms 48724 KB Output is correct
4 Correct 27 ms 2900 KB Output is correct
5 Correct 26 ms 2904 KB Output is correct
6 Correct 1999 ms 378320 KB Output is correct
7 Correct 28 ms 1620 KB Output is correct
8 Incorrect 41 ms 8168 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1512 KB Output is correct
2 Correct 28 ms 3160 KB Output is correct
3 Correct 234 ms 48724 KB Output is correct
4 Correct 27 ms 2900 KB Output is correct
5 Correct 26 ms 2904 KB Output is correct
6 Correct 1999 ms 378320 KB Output is correct
7 Correct 28 ms 1620 KB Output is correct
8 Incorrect 41 ms 8168 KB Output isn't correct
9 Halted 0 ms 0 KB -