oj.uz

Submission #553990

# Submission time Handle Problem Language Result Execution time Memory
553990 2022-04-27T13:24:23 Z Sam_a17 Inside information (BOI21_servers) C++14
5 / 100
 187 ms 20936 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) {
        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: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 1360 KB Output is correct
2 Correct 91 ms 20720 KB Output is correct
3 Correct 95 ms 20872 KB Output is correct
4 Correct 96 ms 20752 KB Output is correct
5 Correct 85 ms 20768 KB Output is correct
6 Correct 112 ms 20868 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1360 KB Output is correct
2 Correct 91 ms 20720 KB Output is correct
3 Correct 95 ms 20872 KB Output is correct
4 Correct 96 ms 20752 KB Output is correct
5 Correct 85 ms 20768 KB Output is correct
6 Correct 112 ms 20868 KB Output is correct
7 Correct 19 ms 1460 KB Output is correct
8 Correct 83 ms 20712 KB Output is correct
9 Correct 97 ms 20936 KB Output is correct
10 Correct 85 ms 20684 KB Output is correct
11 Correct 84 ms 20752 KB Output is correct
12 Correct 123 ms 20928 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1468 KB Output is correct
2 Incorrect 187 ms 4600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1468 KB Output is correct
2 Incorrect 187 ms 4600 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1360 KB Output is correct
2 Incorrect 48 ms 4204 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 1536 KB Output is correct
2 Incorrect 45 ms 4176 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 1536 KB Output is correct
2 Incorrect 45 ms 4176 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1424 KB Output is correct
2 Incorrect 55 ms 4068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1424 KB Output is correct
2 Incorrect 55 ms 4068 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 1364 KB Output is correct
2 Correct 98 ms 20884 KB Output is correct
3 Correct 90 ms 20796 KB Output is correct
4 Correct 90 ms 20736 KB Output is correct
5 Correct 84 ms 20748 KB Output is correct
6 Correct 121 ms 20860 KB Output is correct
7 Correct 21 ms 1596 KB Output is correct
8 Incorrect 177 ms 4632 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 1364 KB Output is correct
2 Correct 98 ms 20884 KB Output is correct
3 Correct 90 ms 20796 KB Output is correct
4 Correct 90 ms 20736 KB Output is correct
5 Correct 84 ms 20748 KB Output is correct
6 Correct 121 ms 20860 KB Output is correct
7 Correct 21 ms 1596 KB Output is correct
8 Incorrect 177 ms 4632 KB Output isn't correct
9 Halted 0 ms 0 KB -