oj.uz

Submission #553964

# Submission time Handle Problem Language Result Execution time Memory
553964 2022-04-27T12:41:12 Z Sam_a17 Inside information (BOI21_servers) C++14
5 / 100
 117 ms 21772 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> stack(n + 1), order(n + 1);
      for(auto qr: queries) {
        int type = qr.first, a = qr.second.first, b = qr.second.second;
        if(type == 'S') {
          stack[it] = max(a, b);
          order[max(a, b)] = it;
          it++;
        } else if(type == 'Q') {
          if(order[a] > order[b]) {
            printf("yes\n");
          } else {
            printf("no\n");
          }
        } else {
          if(a == 1) {
            printf("%d\n", it);
          } else if (!order[a]) {
            printf("1\n");
          } else {
            printf("%d\n", it - order[a] + 1);
          }
        }
      }
    }

  }

}

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 1744 KB Output is correct
2 Correct 90 ms 21624 KB Output is correct
3 Correct 92 ms 21728 KB Output is correct
4 Correct 117 ms 21632 KB Output is correct
5 Correct 89 ms 21640 KB Output is correct
6 Correct 109 ms 21740 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1744 KB Output is correct
2 Correct 90 ms 21624 KB Output is correct
3 Correct 92 ms 21728 KB Output is correct
4 Correct 117 ms 21632 KB Output is correct
5 Correct 89 ms 21640 KB Output is correct
6 Correct 109 ms 21740 KB Output is correct
7 Correct 21 ms 1748 KB Output is correct
8 Correct 98 ms 21356 KB Output is correct
9 Correct 97 ms 21360 KB Output is correct
10 Correct 91 ms 21452 KB Output is correct
11 Correct 101 ms 21360 KB Output is correct
12 Correct 114 ms 21480 KB Output is correct

Subtask #3
0 / 2.5

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

Subtask #4
0 / 2.5

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

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1736 KB Output is correct
2 Incorrect 45 ms 6548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1736 KB Output is correct
2 Incorrect 45 ms 6548 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 1800 KB Output is correct
2 Incorrect 45 ms 6456 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 1800 KB Output is correct
2 Incorrect 45 ms 6456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1792 KB Output is correct
2 Correct 102 ms 21708 KB Output is correct
3 Correct 107 ms 21688 KB Output is correct
4 Correct 99 ms 21772 KB Output is correct
5 Correct 89 ms 21708 KB Output is correct
6 Correct 112 ms 21692 KB Output is correct
7 Correct 21 ms 1752 KB Output is correct
8 Incorrect 50 ms 7344 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 1792 KB Output is correct
2 Correct 102 ms 21708 KB Output is correct
3 Correct 107 ms 21688 KB Output is correct
4 Correct 99 ms 21772 KB Output is correct
5 Correct 89 ms 21708 KB Output is correct
6 Correct 112 ms 21692 KB Output is correct
7 Correct 21 ms 1752 KB Output is correct
8 Incorrect 50 ms 7344 KB Output isn't correct
9 Halted 0 ms 0 KB -