Submission #773046

#	Time	Username	Problem	Language	Result	Execution time	Memory
773046		fuad27	Inside information (BOI21_servers)	C++17	5 / 100	1961 ms	524288 KiB

servers

/*
 * 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
• Subtask 2: 2.5 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5