0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

AtCoder 勉強記録[C++] その63

Posted at

AtCoderで入茶を目指して勉強しています。
勉強を継続するために投稿を始めました。
もともとアカウントを作成していましたが、今年の4月から本格的に勉強を始めました。
一応自分用に解法を書いていますが雑です、自分で読み返して困ったら修正します。
私のアカウント
解いた問題

本日解いた問題

C - Ladder Takahashi

C - Ladder Takahashi
解答

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 998244353

map<int, vector<int>> g;
set<int> seen;
void dfs(int v){
  seen.insert(v);
  for(auto nex:g[v]){
    if(seen.count(nex)) continue;
    dfs(nex);
  }
  
}

int main() {
  int n;
  cin >> n;
  for(int i = 0; i < n; i++){
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs(1);
  cout << *seen.rbegin() << endl;
}

解法

問題のビルが10^9階建てであるため、全てを考えると計算量をオーバーしてしまう。ここで、はしごの数は2*10^5個であるため、はしごのかかった階のみを考えることで計算量を減らす。今回はMap型を用いることではしごのかかった階のみを考える。さらにDFSを用いることで結果がもとまる。

C - FF

C - FF
解答

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 998244353

int main() {
  int n, q;
  cin >> n >> q;
  set<pair<int, int>> f;
  for(int i = 0; i < q; i++){
    int a, b, t;
    cin >> t >> a >> b;
    if(t == 1){
      f.emplace(a,b);
    } else if(t == 2) {
      f.erase({a,b});
    } else {
      if(f.count({a,b}) && f.count({b,a})) cout << "Yes" << endl;
      else cout << "No" << endl;
    }
  }
}

解法

AがBをフォローしている関係をpair型配列を用いて(A,B)と表す。この関係を管理するset型を用意しておき、T=1の場合は(A,B)を追加、T=2の場合は(A,B)を削除、T=3の場合は(A,B)(B,A)ともに存在する場合Yesを、存在しない場合Noを出力する。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?