oj.uz

Submission #553987

# Submission time Handle Problem Language Result Execution time Memory
553987 2022-04-27T13:22:23 Z Sam_a17 Inside information (BOI21_servers) C++14
5 / 100
 182 ms 20816 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);
      order[1] = 0;
      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(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: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 19 ms 1228 KB Output is correct
2 Correct 86 ms 20628 KB Output is correct
3 Correct 87 ms 20648 KB Output is correct
4 Correct 91 ms 20704 KB Output is correct
5 Correct 85 ms 20684 KB Output is correct
6 Correct 112 ms 20712 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1228 KB Output is correct
2 Correct 86 ms 20628 KB Output is correct
3 Correct 87 ms 20648 KB Output is correct
4 Correct 91 ms 20704 KB Output is correct
5 Correct 85 ms 20684 KB Output is correct
6 Correct 112 ms 20712 KB Output is correct
7 Correct 19 ms 1236 KB Output is correct
8 Correct 86 ms 20572 KB Output is correct
9 Correct 94 ms 20696 KB Output is correct
10 Correct 91 ms 20564 KB Output is correct
11 Correct 83 ms 20516 KB Output is correct
12 Correct 111 ms 20796 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1272 KB Output is correct
2 Incorrect 180 ms 4808 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 1272 KB Output is correct
2 Incorrect 180 ms 4808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1240 KB Output is correct
2 Incorrect 45 ms 4212 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 1240 KB Output is correct
2 Incorrect 45 ms 4212 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 1212 KB Output is correct
2 Incorrect 46 ms 4120 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 1212 KB Output is correct
2 Incorrect 46 ms 4120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1228 KB Output is correct
2 Correct 88 ms 20684 KB Output is correct
3 Correct 94 ms 20704 KB Output is correct
4 Correct 91 ms 20812 KB Output is correct
5 Correct 88 ms 20816 KB Output is correct
6 Correct 116 ms 20708 KB Output is correct
7 Correct 20 ms 1240 KB Output is correct
8 Incorrect 182 ms 4792 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1228 KB Output is correct
2 Correct 88 ms 20684 KB Output is correct
3 Correct 94 ms 20704 KB Output is correct
4 Correct 91 ms 20812 KB Output is correct
5 Correct 88 ms 20816 KB Output is correct
6 Correct 116 ms 20708 KB Output is correct
7 Correct 20 ms 1240 KB Output is correct
8 Incorrect 182 ms 4792 KB Output isn't correct
9 Halted 0 ms 0 KB -