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