oj.uz

Submission #730656

# Submission time Handle Problem Language Result Execution time Memory
730656 2023-04-26T08:52:23 Z Sam_a17 Inside information (BOI21_servers) C++17
5 / 100
 113 ms 21732 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) {
      assert(false);
      int it = 1;
      vector<int> order(n + 1, 1e8);
      order[1] = 0;
      for (auto qr: queries) {
        char type = qr.first;
        int 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(a == 1 || b == 1) {
            cout << "yes" << 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: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 + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:69:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:74:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1744 KB Output is correct
2 Correct 81 ms 21628 KB Output is correct
3 Correct 81 ms 21700 KB Output is correct
4 Correct 84 ms 21608 KB Output is correct
5 Correct 84 ms 21620 KB Output is correct
6 Correct 102 ms 21652 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1744 KB Output is correct
2 Correct 81 ms 21628 KB Output is correct
3 Correct 81 ms 21700 KB Output is correct
4 Correct 84 ms 21608 KB Output is correct
5 Correct 84 ms 21620 KB Output is correct
6 Correct 102 ms 21652 KB Output is correct
7 Correct 18 ms 1748 KB Output is correct
8 Correct 78 ms 21296 KB Output is correct
9 Correct 102 ms 21404 KB Output is correct
10 Correct 96 ms 21320 KB Output is correct
11 Correct 86 ms 21304 KB Output is correct
12 Correct 101 ms 21452 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1832 KB Output is correct
2 Runtime error 66 ms 9332 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1832 KB Output is correct
2 Runtime error 66 ms 9332 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1828 KB Output is correct
2 Incorrect 49 ms 6468 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 1828 KB Output is correct
2 Incorrect 49 ms 6468 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 1820 KB Output is correct
2 Incorrect 48 ms 6476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1820 KB Output is correct
2 Incorrect 48 ms 6476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1720 KB Output is correct
2 Correct 91 ms 21708 KB Output is correct
3 Correct 112 ms 21732 KB Output is correct
4 Correct 85 ms 21608 KB Output is correct
5 Correct 89 ms 21600 KB Output is correct
6 Correct 113 ms 21724 KB Output is correct
7 Correct 22 ms 1736 KB Output is correct
8 Runtime error 51 ms 9312 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1720 KB Output is correct
2 Correct 91 ms 21708 KB Output is correct
3 Correct 112 ms 21732 KB Output is correct
4 Correct 85 ms 21608 KB Output is correct
5 Correct 89 ms 21600 KB Output is correct
6 Correct 113 ms 21724 KB Output is correct
7 Correct 22 ms 1736 KB Output is correct
8 Runtime error 51 ms 9312 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -