Bùi Hùng Nam NamPE286
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef long long ll; | |
| vector<ll> LIS(vector<ll> &a) { | |
| vector<ll> dp(1); // dp[i] = ending of LIS with length i | |
| vector<ll> pos(1); // pos[i] = LIS with length i last element index in a | |
| unordered_map<ll, ll> parent; // parent index of a[i] in LIS, -1 mean first element | |
| for (ll i = 0; i < a.size(); i++) { |
NamPE286
/ segmented_sieve.cpp
Last active
May 28, 2023 06:27
Segmented sieve of Eratosthenes implementation in C++
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef long long ll; | |
| vector<ll> sieve(ll n) { | |
| vector<ll> is_prime(n + 1, true), res; | |
| for (ll i = 2; i <= n; i++) { | |
| if (is_prime[i]) { | |
| res.push_back(i); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef long long ll; | |
| vector<vector<ll>> sieve(ll n){ | |
| vector<vector<ll>> fact(n + 1); | |
| for(ll i = 2; i <= n; i++){ | |
| if(fact[i].empty()){ | |
| for(ll j = i; j <= n; j += i){ |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef long long ll; | |
| template <typename T> | |
| class general_tree { | |
| private: | |
| T root; | |
| bool modified = false; |
NamPE286
/ shortest_unweighted.cpp
Created
April 18, 2023 19:27
Shortest path in unweighted path with BFS
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // https://cses.fi/problemset/result/5916157/ | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef long long ll; | |
| vector<ll> bfs(vector<vector<ll>> &graph, ll n) { | |
| vector<ll> parent(n + 1); | |
| queue<ll> q; | |
| q.push(1); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef long long ll; | |
| struct item { | |
| ll node; | |
| ll weight; | |
| bool operator<(const item &y) const { return weight > y.weight; } | |
| }; |
NamPE286
/ floyd_warshall.cpp
Created
April 19, 2023 00:59
Floyd Warshall's algorithm implementation in C++ (used to calculate all vertex pair distance) (better than dijkstra when E > V^3)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef long long ll; | |
| int main(){ | |
| ios::sync_with_stdio(0); | |
| cout.tie(0); | |
| cin.tie(0); | |
| ll n, m, q; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef long long ll; | |
| bool isDAG(vector<vector<ll>> &graph, vector<ll> &color, ll u){ | |
| color[u] = 1; | |
| for(ll i : graph[u]){ | |
| if(color[i] == 0){ | |
| if (!isDAG(graph, color, i)) return false; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // https://cses.fi/problemset/task/1679/ | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef long long ll; | |
| void dfs(vector<vector<ll>> &graph, vector<bool> &visited, vector<ll> &topsort, ll u) { | |
| if (visited[u]) return; | |
| visited[u] = true; | |
| for (ll i : graph[u]) { |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // https://cses.fi/problemset/task/1678/ | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef long long ll; | |
| bool findCycle(vector<vector<ll>> &graph, vector<bool> &visited, vector<bool> &on_stack, vector<ll> &cycle, ll u) { | |
| visited[u] = true, on_stack[u] = true; | |
| for (ll i : graph[u]) { | |
| if (on_stack[i]) { // encounter a cycle |