oj.uz

Submission #553983

# Submission time Handle Problem Language Result Execution time Memory
553983 2022-04-27T13:07:16 Z Sam_a17 Inside information (BOI21_servers) C++14
5 / 100
 185 ms 21844 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
// #include "temp.cpp"
#include <cstdio>
using namespace std;

#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif

#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) x.clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt __builtin_popcount

#define pb push_back
#define pf push_front
#define popf pop_front
#define popb pop_back

void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}

template <class T> void print(set <T> v);
template <class T> void print(vector <T> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T, class V> void print(pair <T, V> p);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque<T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(unordered_map<T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'

// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};

// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}

// file in/out
void setIO(string str = "") {
  fastIO();

  if (str != "" && str != "input") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }

  if(str == "input") {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 4e4 + 10;
int n, q, C[N];
bitset<N> adj[N];

void solve_() {
  cin >> n >> q;

  if (n <= 4000) {
    for (int i = 1; i <= n; i++) {
      adj[i][i] = 1;
      C[i]++, adj[i][N - 1] = 1;
    }

    q += (n - 1);
    while (q--) {
      char type;
      cin >> type;
      if (type == 'S') {
        int a, b;
        cin >> a >> b;

        bitset<N> x = adj[b], y = adj[a];
        adj[b] = adj[b] | adj[a];
        adj[a] = adj[b];
        for (int i = 1; i <= n; i++) {
          if (adj[b][i] != x[i]) {
            C[i]++;
          }
        }

        for (int i = 1; i <= n; i++) {
          if (adj[a][i] != y[i]) {
            C[i]++;
          }
        }
      } else if (type == 'Q') {
        int a, b;
        cin >> a >> b;
        if (adj[a][b]) {
          printf("yes\n");
        } else {
          printf("no\n");
        }
      } else {
        int a;
        cin >> a;
        printf("%d\n", C[a]);
      }
    }
  } else {

    vector<pair<char, pair<int, int>>> queries;
    q += (n - 1);

    bool flag1 = true;

    while (q--) {
      char type;
      cin >> type;
      if (type == 'S' || type == 'Q') {
        int a, b;
        cin >> a >> b;
        queries.pb({type, {a, b}});
        if (type == 'S' && min(a, b) != 1) {
          flag1 = false;
        }
      } else {
        int a;
        cin >> a;
        queries.pb({type, {a, -1}});
      }
    }

    if (flag1) {
      int it = 1;
      vector<int> order(n + 1, 1e8);
      for (auto qr: queries) {
        int type = qr.first, a = qr.second.first, b = qr.second.second;
        if (type == 'S') {
          order[max(a, b)] = it++;
        } else if (type == 'Q') {
          if (order[a] == 1e8 || order[b] == 1e8) {
            cout << "no" << endl;
            continue;
          }
          if (order[a] > order[b]) {
            cout << "yes" << endl;
          } else {
            cout << "no" << endl;
          }
        } else {
          if (a == 1) {
            cout << it << endl;
          } else if (order[a] == 1e8) {
            cout << 1 << endl;
          } else {
            cout << it - order[a] + 1 << endl;
          }
        }
      }
    }
  }
}

int main() {
  setIO();

  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };

  int test_cases = 1;
  solve(test_cases);

  return 0;
}

Compilation message

servers.cpp: In function 'void setIO(std::string)':
servers.cpp:67:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:68:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:72:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:73:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1748 KB Output is correct
2 Correct 85 ms 21684 KB Output is correct
3 Correct 87 ms 21672 KB Output is correct
4 Correct 83 ms 21676 KB Output is correct
5 Correct 85 ms 21772 KB Output is correct
6 Correct 114 ms 21700 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1748 KB Output is correct
2 Correct 85 ms 21684 KB Output is correct
3 Correct 87 ms 21672 KB Output is correct
4 Correct 83 ms 21676 KB Output is correct
5 Correct 85 ms 21772 KB Output is correct
6 Correct 114 ms 21700 KB Output is correct
7 Correct 19 ms 1708 KB Output is correct
8 Correct 82 ms 21288 KB Output is correct
9 Correct 89 ms 21384 KB Output is correct
10 Correct 89 ms 21324 KB Output is correct
11 Correct 86 ms 21348 KB Output is correct
12 Correct 109 ms 21484 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1748 KB Output is correct
2 Incorrect 179 ms 6440 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 1748 KB Output is correct
2 Incorrect 179 ms 6440 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1740 KB Output is correct
2 Incorrect 49 ms 5632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1740 KB Output is correct
2 Incorrect 49 ms 5632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1768 KB Output is correct
2 Incorrect 46 ms 5600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1768 KB Output is correct
2 Incorrect 46 ms 5600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1808 KB Output is correct
2 Correct 85 ms 21596 KB Output is correct
3 Correct 89 ms 21712 KB Output is correct
4 Correct 86 ms 21616 KB Output is correct
5 Correct 83 ms 21668 KB Output is correct
6 Correct 109 ms 21844 KB Output is correct
7 Correct 19 ms 1840 KB Output is correct
8 Incorrect 185 ms 6420 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1808 KB Output is correct
2 Correct 85 ms 21596 KB Output is correct
3 Correct 89 ms 21712 KB Output is correct
4 Correct 86 ms 21616 KB Output is correct
5 Correct 83 ms 21668 KB Output is correct
6 Correct 109 ms 21844 KB Output is correct
7 Correct 19 ms 1840 KB Output is correct
8 Incorrect 185 ms 6420 KB Output isn't correct
9 Halted 0 ms 0 KB -