oj.uz

Submission #598404

# Submission time Handle Problem Language Result Execution time Memory
598404 2022-07-18T09:13:23 Z gagik_2007 Inside information (BOI21_servers) C++17
10 / 100
 408 ms 58260 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;

string findSum(string str1, string str2)
{
    if (str1.length() > str2.length())
        swap(str1, str2);
    string str = "";
    int n1 = str1.length(), n2 = str2.length();
    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
    int carry = 0;
    for (int i = 0; i < n1; i++)
    {
        int sum = ((str1[i] - '0') + (str2[i] - '0') + carry);
        str.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    for (int i = n1; i < n2; i++)
    {
        int sum = ((str2[i] - '0') + carry);
        str.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    if (carry)
        str.push_back(carry + '0');
    reverse(str.begin(), str.end());
    return str;
}
bool isSmaller(string str1, string str2)
{
    int n1 = str1.length(), n2 = str2.length();
    if (n1 < n2)
        return true;
    if (n2 < n1)
        return false;
    for (int i = 0; i < n1; i++)
        if (str1[i] < str2[i])
            return true;
        else if (str1[i] > str2[i])
            return false;
    return false;
}
string findDiff(string str1, string str2)
{
    if (isSmaller(str1, str2))
        swap(str1, str2);
    string str = "";
    int n1 = str1.length(), n2 = str2.length();
    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
    int carry = 0;
    for (int i = 0; i < n2; i++) {
        int sub
            = ((str1[i] - '0') - (str2[i] - '0') - carry);
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
        str.push_back(sub + '0');
    }
    for (int i = n2; i < n1; i++) {
        int sub = ((str1[i] - '0') - carry);
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
        str.push_back(sub + '0');
    }
    reverse(str.begin(), str.end());
    return str;
}

typedef long long ll;
typedef long double ld;
typedef ll itn;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 32768;
const ll N = 100007;
ll n, m, k;
ll t[200007];
bool d[4007][4007];
ll c[4007];
vector<int>g[4007];
ll timer = 1;

int main() {
    cin >> n >> k;
    if (n <= 4000) {
        for (int i = 1; i <= n; i++) {
            d[i][i] = true;
            c[i] = 1;
            g[i].push_back(i);
        }
        for (int i = 0; i < n + k - 1; i++) {
            char typ;
            cin >> typ;
            if (typ == 'S') {
                ll x, y;
                cin >> x >> y;
                vector<int>v;
                for (int vl : g[x]) {
                    d[y][vl] = true;
                    c[vl]++;
                    v.push_back(vl);
                }
                for (int vl : g[y]) {
                    d[x][vl] = true;
                    c[vl]++;
                    v.push_back(vl);
                }
                g[x].clear();
                g[y].clear();
                for (int i = 0; i < v.size(); i++) {
                    g[x].push_back(v[i]);
                    g[y].push_back(v[i]);
                }
            }
            else if (typ == 'Q') {
                ll x, y;
                cin >> x >> y;
                cout << (d[x][y] ? "yes" : "no") << endl;
            }
            else {
                ll x;
                cin >> x;
                cout << c[x] << endl;
            }
        }
    }
    else {
        for (int i = 0; i < n + k - 1; i++) {
            char typ;
            cin >> typ;
            if (typ == 'S') {
                ll x, y;
                cin >> x >> y;
                t[x + y - 1] = timer++;
            }
            else if (typ == 'Q') {
                ll x, y;
                cin >> x >> y;
                if (x == y)cout << "yes\n";
                else if (x == 1) {
                    cout << (t[y] ? "yes" : "no") << endl;
                }
                else if (y == 1) {
                    cout << (t[x] ? "yes" : "no") << endl;
                }
                else if (!t[x] || !t[y] || (t[y] >= t[x])) {
                    cout << "no\n";
                }
                else cout << "yes\n";
            }
            else {
                ll x;
                cin >> x;
                if (x != 1 && !t[x]) {
                    cout << 1 << endl;
                }
                else {
                    cout << timer - t[x] + 1 - (x == 1) << endl;
                }
            }
        }
    }
}

/*
6 13
C 1
S 1 2
S 1 3
C 3
C 4
S 1 4
Q 5 1
C 1
S 1 5
S 1 6
Q 5 1
Q 1 5
Q 4 5
Q 6 5
Q 5 5
C 2
C 5
C 6
*/

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:140:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |                 for (int i = 0; i < v.size(); i++) {
      |                                 ~~^~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 186 ms 1432 KB Output is correct
2 Correct 218 ms 18056 KB Output is correct
3 Correct 237 ms 24232 KB Output is correct
4 Correct 219 ms 17996 KB Output is correct
5 Correct 251 ms 17996 KB Output is correct
6 Correct 357 ms 58240 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 186 ms 1432 KB Output is correct
2 Correct 218 ms 18056 KB Output is correct
3 Correct 237 ms 24232 KB Output is correct
4 Correct 219 ms 17996 KB Output is correct
5 Correct 251 ms 17996 KB Output is correct
6 Correct 357 ms 58240 KB Output is correct
7 Correct 200 ms 1820 KB Output is correct
8 Correct 207 ms 17856 KB Output is correct
9 Correct 244 ms 25696 KB Output is correct
10 Correct 219 ms 17648 KB Output is correct
11 Correct 210 ms 17684 KB Output is correct
12 Correct 342 ms 58004 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 213 ms 1004 KB Output is correct
2 Correct 293 ms 2260 KB Output is correct
3 Correct 328 ms 1740 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 213 ms 1004 KB Output is correct
2 Correct 293 ms 2260 KB Output is correct
3 Correct 328 ms 1740 KB Output is correct
4 Correct 188 ms 1036 KB Output is correct
5 Correct 270 ms 1760 KB Output is correct
6 Correct 230 ms 2024 KB Output is correct
7 Correct 240 ms 1868 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 1376 KB Output is correct
2 Runtime error 1 ms 724 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 1376 KB Output is correct
2 Runtime error 1 ms 724 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 1448 KB Output is correct
2 Incorrect 313 ms 5420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 1448 KB Output is correct
2 Incorrect 313 ms 5420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 191 ms 1480 KB Output is correct
2 Runtime error 1 ms 724 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 191 ms 1480 KB Output is correct
2 Runtime error 1 ms 724 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 198 ms 1360 KB Output is correct
2 Correct 239 ms 18116 KB Output is correct
3 Correct 244 ms 24004 KB Output is correct
4 Correct 249 ms 17996 KB Output is correct
5 Correct 230 ms 17960 KB Output is correct
6 Correct 408 ms 58260 KB Output is correct
7 Correct 190 ms 1860 KB Output is correct
8 Correct 274 ms 4636 KB Output is correct
9 Correct 271 ms 4512 KB Output is correct
10 Correct 198 ms 1800 KB Output is correct
11 Runtime error 1 ms 724 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 198 ms 1360 KB Output is correct
2 Correct 239 ms 18116 KB Output is correct
3 Correct 244 ms 24004 KB Output is correct
4 Correct 249 ms 17996 KB Output is correct
5 Correct 230 ms 17960 KB Output is correct
6 Correct 408 ms 58260 KB Output is correct
7 Correct 190 ms 1860 KB Output is correct
8 Correct 274 ms 4636 KB Output is correct
9 Correct 271 ms 4512 KB Output is correct
10 Correct 198 ms 1800 KB Output is correct
11 Runtime error 1 ms 724 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -