oj.uz

Submission #899125

# Submission time Handle Problem Language Result Execution time Memory
899125 2024-01-05T13:49:13 Z Nahian9696 Inside information (BOI21_servers) C++17
10 / 100
 1799 ms 377016 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;
}


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;

    // 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];

        } 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());
            print(left[a]+right[a]-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 604 KB Output is correct
2 Correct 27 ms 2140 KB Output is correct
3 Correct 229 ms 47860 KB Output is correct
4 Correct 26 ms 1880 KB Output is correct
5 Correct 25 ms 1800 KB Output is correct
6 Correct 1799 ms 376964 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 604 KB Output is correct
2 Correct 27 ms 2140 KB Output is correct
3 Correct 229 ms 47860 KB Output is correct
4 Correct 26 ms 1880 KB Output is correct
5 Correct 25 ms 1800 KB Output is correct
6 Correct 1799 ms 376964 KB Output is correct
7 Correct 17 ms 604 KB Output is correct
8 Correct 24 ms 2140 KB Output is correct
9 Correct 268 ms 59996 KB Output is correct
10 Correct 23 ms 1876 KB Output is correct
11 Correct 24 ms 1884 KB Output is correct
12 Correct 1770 ms 376976 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 860 KB Output is correct
2 Incorrect 37 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 860 KB Output is correct
2 Incorrect 37 ms 2652 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 21 ms 600 KB Output is correct
2 Correct 42 ms 2516 KB Output is correct
3 Correct 45 ms 2640 KB Output is correct
4 Correct 38 ms 5916 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 600 KB Output is correct
2 Correct 42 ms 2516 KB Output is correct
3 Correct 45 ms 2640 KB Output is correct
4 Correct 38 ms 5916 KB Output is correct
5 Correct 17 ms 1684 KB Output is correct
6 Incorrect 39 ms 5716 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 17 ms 856 KB Output is correct
2 Incorrect 37 ms 2472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 856 KB Output is correct
2 Incorrect 37 ms 2472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 660 KB Output is correct
2 Correct 43 ms 2648 KB Output is correct
3 Correct 39 ms 2672 KB Output is correct
4 Correct 38 ms 5892 KB Output is correct
5 Correct 17 ms 1628 KB Output is correct
6 Incorrect 51 ms 5900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 660 KB Output is correct
2 Correct 43 ms 2648 KB Output is correct
3 Correct 39 ms 2672 KB Output is correct
4 Correct 38 ms 5892 KB Output is correct
5 Correct 17 ms 1628 KB Output is correct
6 Incorrect 51 ms 5900 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 600 KB Output is correct
2 Correct 29 ms 2128 KB Output is correct
3 Correct 222 ms 47696 KB Output is correct
4 Correct 26 ms 1840 KB Output is correct
5 Correct 27 ms 1628 KB Output is correct
6 Correct 1786 ms 377016 KB Output is correct
7 Correct 18 ms 856 KB Output is correct
8 Incorrect 44 ms 2704 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 600 KB Output is correct
2 Correct 29 ms 2128 KB Output is correct
3 Correct 222 ms 47696 KB Output is correct
4 Correct 26 ms 1840 KB Output is correct
5 Correct 27 ms 1628 KB Output is correct
6 Correct 1786 ms 377016 KB Output is correct
7 Correct 18 ms 856 KB Output is correct
8 Incorrect 44 ms 2704 KB Output isn't correct
9 Halted 0 ms 0 KB -