oj.uz

Submission #773046

# Submission time Handle Problem Language Result Execution time Memory
773046 2023-07-04T14:21:14 Z fuad27 Inside information (BOI21_servers) C++17
5 / 100
 1961 ms 524288 KB 
/*
 * Author: fuad720
 * Time: 2023-07-04 18:11
*/

// =========== Template ========== //

#ifndef LOCAL
  #pragma GCC optimize("O3,unroll-loops")
  #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  #include <bits/stdc++.h>
  #include <ext/pb_ds/assoc_container.hpp>
  #include <ext/pb_ds/tree_policy.hpp>
#else
  #include "/home/fuad/cp/all.h"
#endif
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using oset =
  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using omset =
  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

using ll = long long;
using ull = unsigned long long;
using ld=long double;
using lll = __int128_t;
using ulll = __uint128_t;
#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) FOR(i,0,b)
#define FORN(i,a,b) for(int i=int(b)-1;i>=a;i--)
#define per(i,b) FORN(i,0,b)

#define mkp make_pair
#define pb push_back
#define ep emplace_back
#define ins insert
#define ff first
#define ss second
#define bg begin()
#define ed end()
#define sz(x) (int)x.size()
#define all(x) (x).bg,(x).ed
#define FIO ios_base::sync_with_stdio(0);\
  cin.tie(0);

template<class t> using vc=vector<t>;;
template<class t> using vvc=vc<vc<t>>;
template<class F, class S> using pr=pair<F,S>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi= vc<int>;
using vll= vc<ll>;
#define mset multiset
#define umap unordered_map
#define pqueue priority_queue

int nxt() {
  int x;
  cin >> x;
  return x;
}
ll nxtll() {
  ll x;
  cin >> x;
  return x;
}


#ifdef LOCAL
#include "/home/fuad/cp/dbg.h"
#else
#define dbg(x...)
#endif
const ll INFL=(ll)1e18;
const int INF=(ll)2e9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngll(chrono::steady_clock::now().time_since_epoch().count());

// =========== Solution ========== //
const int N=120010;
void solve() {
  int n, k;
  cin >> n >> k;
  k+=n-1;
  bitset<N> B[n];
  for(int i = 0;i<n;i++)B[i][i]=1;
  while(k--) {
    string s;
    cin >> s;
    dbg(s);
    if(s[0]=='S') {
      int a, b;
      cin >> a >> b;
      a--,b--;
      B[a]|=B[b];
      B[b]|=B[a];
    }
    else if(s[0]=='Q') {
      int a, b;
      cin >> a >> b;
      a--,b--;
      cout << (B[a][b]?"yes":"no") << "\n";
    }
    else {
      int c;
      cin >> c;
      c--;
      int cnt=0;
      for(int i = 0;i<n;i++) {
        cnt+=B[i][c];
      }
      cout << cnt << "\n";
    }
  }
}

signed main () {
  FIO;
  int t=1;
  while(t--)
    solve();
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1320 KB Output is correct
2 Correct 69 ms 60760 KB Output is correct
3 Correct 61 ms 60752 KB Output is correct
4 Correct 67 ms 60728 KB Output is correct
5 Correct 64 ms 60720 KB Output is correct
6 Correct 61 ms 60844 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1320 KB Output is correct
2 Correct 69 ms 60760 KB Output is correct
3 Correct 61 ms 60752 KB Output is correct
4 Correct 67 ms 60728 KB Output is correct
5 Correct 64 ms 60720 KB Output is correct
6 Correct 61 ms 60844 KB Output is correct
7 Correct 23 ms 2156 KB Output is correct
8 Correct 1829 ms 60440 KB Output is correct
9 Correct 1900 ms 60548 KB Output is correct
10 Correct 1891 ms 60568 KB Output is correct
11 Correct 1961 ms 60524 KB Output is correct
12 Correct 1912 ms 60528 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1420 KB Output is correct
2 Runtime error 266 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1420 KB Output is correct
2 Runtime error 266 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1452 KB Output is correct
2 Runtime error 188 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1452 KB Output is correct
2 Runtime error 188 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1620 KB Output is correct
2 Runtime error 206 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1620 KB Output is correct
2 Runtime error 206 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1532 KB Output is correct
2 Runtime error 162 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1532 KB Output is correct
2 Runtime error 162 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1516 KB Output is correct
2 Correct 73 ms 60692 KB Output is correct
3 Correct 75 ms 60748 KB Output is correct
4 Correct 72 ms 60684 KB Output is correct
5 Correct 71 ms 60708 KB Output is correct
6 Correct 69 ms 60796 KB Output is correct
7 Correct 22 ms 2260 KB Output is correct
8 Runtime error 165 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1516 KB Output is correct
2 Correct 73 ms 60692 KB Output is correct
3 Correct 75 ms 60748 KB Output is correct
4 Correct 72 ms 60684 KB Output is correct
5 Correct 71 ms 60708 KB Output is correct
6 Correct 69 ms 60796 KB Output is correct
7 Correct 22 ms 2260 KB Output is correct
8 Runtime error 165 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -