Skip to content

Instantly share code, notes, and snippets.

@shinkeonkim

shinkeonkim/cpp.json

Created May 18, 2022 15:26
Show Gist options
  • Save shinkeonkim/e60c3b9cd93567c74a975969b8eef794 to your computer and use it in GitHub Desktop.
Save shinkeonkim/e60c3b9cd93567c74a975969b8eef794 to your computer and use it in GitHub Desktop.
Download ZIP
ps-vscode-snippet
Raw
cpp.json
{
"ps-start": {
"prefix": "ps",
"body": [
"#include <bits/stdc++.h>",
"",
"#define for1(s,n) for(int i = s; i < n; i++)",
"#define for1j(s,n) for(int j = s; j < n; j++)",
"#define foreach(k) for(auto i : k)",
"#define foreachj(k) for(auto j : k)",
"#define pb(a) push_back(a)",
"#define sz(a) a.size()",
"",
"using namespace std;",
"typedef unsigned long long ull;",
"typedef long long ll;",
"typedef vector <int> iv1;",
"typedef vector <vector<int> > iv2;",
"typedef vector <ll> llv1;",
"typedef unsigned int uint;",
"typedef vector <ull> ullv1;",
"typedef vector <vector <ull> > ullv2;",
"",
"$1",
"int main() {",
" ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);",
" $2",
"}",
],
"description": "ps code snippet"
},
"ccw": {
"prefix": "ccw",
"body": [
"struct point{",
" ll x,y;",
" ll p=0,q=0;",
"};",
"",
"ll ccw(point p1, point p2, point p3) {",
" ll ret = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p2.x * p1.y - p3.x * p2.y - p1.x * p3.y);",
" return ret >0?1:(ret<0?-1:0);",
"}",
],
"description": "ll ccw",
},
"disjoint-set": {
"prefix": "disjoint-set",
"body": [
"void init(int size) {",
" for(int x=1; x<=size; x++) {",
" u[x] = x;",
" }",
"}",
"",
"int find(int k) {",
" if(u[u[k]] == u[k]) return u[k];",
" else return u[k]=find(u[k]);",
"}",
"",
"void uni(int a, int b) {",
" a = find(a);",
" b = find(b);",
" if(a < b) u[b] = a;",
" else u[a] = b; ",
"}",
],
"description": "disjoint-set",
},
"kmp": {
"prefix": "kmp",
"body": [
"int fail[MX];",
"vector <int> kmp (string s, string o) {",
" fill(fail, fail+MX, 0);",
" vector<int> result;",
" int N = s.length();",
" int M = o.length();",
" for(int i=1, j=0; i<M; i++){",
" while(j > 0 && o[i] != o[j]) j = fail[j-1];",
" if(o[i] == o[j]) fail[i] = ++j;",
" }",
" for(int i = 0, j = 0; i < N; i++) {",
" while(j > 0 && s[i] != o[j]) {",
" j = fail[j-1];",
" }",
" if(s[i] == o[j]) {",
" if(j == M-1) {",
" // matching OK;",
" result.push_back(i - M + 2);",
" j = fail[j];",
" }",
" else {",
" j++;",
" }",
" }",
" }",
" return result;",
"}",
],
"description": "kmp matching algorithm",
},
"Trie": {
"prefix": "trie",
"body": [
"const int MX_NODE = 26;",
"",
"int chrToIdx(char ch) { return ch - 'a'; }",
"",
"struct Trie {",
" Trie* children[MX_NODE];",
" bool isEndPoint = false;",
"",
" Trie() {",
" for1(0, MX_NODE) {",
" children[i] = NULL;",
" }",
" }",
"",
" ~Trie() {",
" for1(0, MX_NODE) {",
" if(children[i]) delete children[i];",
" }",
" }",
" ",
" void insert(string& s, int idx = 0) {",
" if(idx == s.size()) {",
" isEndPoint = true;",
" return;",
" }",
" int nextIdx = chrToIdx(s[idx]);",
" if(children[nextIdx] == NULL) {",
" children[nextIdx] = new Trie();",
" }",
" children[nextIdx]->insert(s, idx+1);",
" }",
" ",
" bool find(string& s, int idx = 0) {",
" if(idx == s.size()) {",
" return isEndPoint;",
" }",
" int nextIdx = chrToIdx(s[idx]);",
" if(children[nextIdx] == NULL) {",
" return false;",
" }",
" return children[nextIdx]->find(s, idx+1);",
" }",
"};",
]
},
"Dijkstra": {
"prefix": "dijkstra",
"body": [
"struct edge {",
" ll node;",
" ll cost;",
" bool operator<(const edge &to) const {",
" return cost > to.cost;",
" }",
"};",
"",
"struct WGraph {",
" ll n; ",
" vector<vector<edge>> adj;",
" vector<ll> prev;",
" WGraph(ll n) : n{n}, adj(n+1) {}",
" void addEdge(ll s, ll e, ll cost) {",
" adj[s].push_back({e, cost});",
" }",
"",
" void input(ll m) { // 단방향",
" ll a, b, c;",
" while(m--) {",
" cin >> a >> b >> c;",
" addEdge(a,b,c);",
" }",
" }",
"",
" void inputD(ll m) { // 양방향",
" ll a, b, c;",
" while(m--){",
" cin >> a >> b >> c;",
" addEdge(a,b,c);",
" addEdge(b,a,c);",
" }",
" }",
"",
" vector <ll> dijkstra(ll s) {",
" vector <ll> dist(n+1, INF);",
" prev.resize(n+1, -1);",
" priority_queue<edge> pq;",
" pq.push({ s, 0ll });",
" dist[s] = 0;",
" while (!pq.empty()) {",
" edge cur = pq.top();",
" pq.pop();",
" if (cur.cost > dist[cur.node]) continue;",
" for (auto &nxt : adj[cur.node])",
" if (dist[cur.node] + nxt.cost < dist[nxt.node]) {",
" prev[nxt.node] = cur.node;",
" dist[nxt.node] = dist[cur.node] + nxt.cost;",
" pq.push({ nxt.node, dist[nxt.node] });",
" }",
" }",
" return dist;",
" }",
"",
" vector<ll> getPath(ll s, ll e) {",
" vector<ll> ret;",
" ll current = e;",
" while(current != -1) {",
" ret.push_back(current);",
" current = prev[current];",
" }",
" reverse(ret.begin(), ret.end());",
" return ret;",
" }",
"};"
]
},
"prim": {
"prefix": "prim",
"body": [
"struct edge {",
" ll crt;",
" ll node, cost;",
"};",
"",
"struct WGraph {",
" ll V; ",
" vector<edge> adj[MAX];",
" vector<ll> prev;",
" WGraph(ll V) : V{V} {}",
" void addEdge(ll s, ll e, ll cost) {",
" adj[s].push_back({s, e, cost});",
" adj[e].push_back({e, s, cost});",
" }",
" ",
" ll prim(vector<edge> &selected) { // selected에 선택된 간선정보 vector 담김",
" selected.clear();",
" ",
" vector<bool> added(V, false);",
" llv1 minWeight(V, INF), parent(V, -1);",
" ",
" ll ret = 0;",
" minWeight[0] = parent[0] = 0;",
" for (int iter = 0; iter < V; iter++) {",
" int u = -1;",
" for (int v = 0; v < V; v++) {",
" if (!added[v] && (u == -1 || minWeight[u]>minWeight[v]))",
" u = v;",
" }",
" ",
" if (parent[u] != u)",
" selected.push_back({parent[u], u, minWeight[u]});",
" ",
" ret += minWeight[u];",
" added[u] = true;",
"",
" for1(0, sz(adj[u])) {",
" int v = adj[u][i].node, weight = adj[u][i].cost;",
" if (!added[v] && minWeight[v]>weight) {",
" parent[v] = u;",
" minWeight[v] = weight;",
" }",
" }",
" }",
" return ret;",
" }",
"};"
]
},
"2_sat": {
"prefix": "2_sat",
"body": [
"struct two_sat {",
" int v, e;",
" iv2 edge;",
" iv2 edgePrime;",
" iv2 scc;",
" bool visited[MX];",
" bool visitedPrime[MX];",
" int finishTimeNode[MX];",
" int current;",
"",
" two_sat(int _v, int _e) : v(_v), e(_e) {",
" int mx = 2*_v+1;",
" edge.assign(mx, iv1(0));",
" edgePrime.assign(mx, iv1(0));",
" scc.clear();",
" fill(visited, visited+mx, 0);",
" fill(visitedPrime, visitedPrime+mx, 0);",
" fill(finishTimeNode, finishTimeNode+mx, 0);",
" current = 0;",
" }",
"",
" int not_num(int num) {",
" return num > v ? num - v : num + v;",
" }",
"",
" void add_edge(int a, int b) {",
" if(a < 0) a = -a + v;",
" if(b < 0) b = -b + v;",
"",
" edge[not_num(a)].pb(b);",
" edgePrime[b].pb(not_num(a));",
" edge[not_num(b)].pb(a);",
" edgePrime[a].pb(not_num(b));",
" }",
"",
" void set_scc() {",
" for1(1, 2*v+1) {",
" if(!visited[i]) {",
" dfs(i);",
" }",
" }",
" for(int t = 2*v; t >= 1; t--) {",
" int r = finishTimeNode[t];",
" if(!visitedPrime[r]) {",
" iv1 current_scc;",
" reverse_dfs(r, current_scc);",
" sort(current_scc.begin(), current_scc.end());",
" scc.push_back(current_scc);",
" }",
" }",
"",
" sort(scc.begin(), scc.end());",
" } ",
"",
" void dfs(int node) {",
" visited[node] = true;",
" foreach(edge[node]) {",
" if(!visited[i]) {",
" dfs(i);",
" }",
" }",
" finishTimeNode[++current] = node;",
" }",
"",
" void reverse_dfs(int node, iv1& current_scc) {",
" current_scc.pb(node);",
" visitedPrime[node] = true;",
" foreach(edgePrime[node]) {",
" if(!visitedPrime[i]) {",
" reverse_dfs(i, current_scc);",
" }",
" }",
" }",
"",
" bool is_valid() {",
" foreach(scc) {",
" map<int, int> m;",
" foreachj(i) {",
" m[j] = 1;",
" if(m.find(not_num(j)) != m.end()) {",
" return false;",
" }",
" }",
" }",
" return true;",
" }",
"};",
],
"description": "2_sat, require: get_scc",
},
"lis-only-length": {
"prefix": "lisol",
"description": "Longest Icreasing Sequence Length",
"body": [
"ll lis(llv1 ar) {",
" llv1 v, buffer;",
" llv1::iterator vv;",
" v.pb(2000000000ll);",
"",
" ll n = sz(ar);",
"",
" for1(0, n){",
" if(ar[i] > *v.rbegin()) {",
" v.pb(ar[i]);",
" }",
" else{",
" vv = lower_bound(v.begin(), v.end(), ar[i]);",
" *vv = ar[i];",
" }",
" }",
" return sz(v);",
"}"
]
},
"lis": {
"prefix": "lis",
"description": "Longest Icreasing Sequence",
"body": [
"llv1 lis(llv1 ar) {",
" llv1 v, buffer;",
" llv1::iterator vv;",
" vector<pair<ll, ll> > d;",
" v.pb(2000000000ll);",
"",
" ll n = sz(ar);",
"",
" for1(0, n){",
" if (ar[i] > *v.rbegin()) {",
" v.pb(ar[i]);",
" d.push_back({ v.size() - 1, ar[i] });",
" }",
" else {",
" vv = lower_bound(v.begin(), v.end(), ar[i]);",
" *vv = ar[i];",
" d.push_back({ vv - v.begin(), ar[i] });",
" }",
" }",
" ",
" for(int i = sz(d) - 1; i > -1; i--){",
" if(d[i].first == sz(v)-1){",
" buffer.pb(d[i].second);",
" v.pop_back();",
" }",
" }",
"",
" reverse(buffer.begin(), buffer.end());",
"",
" return buffer;",
"}"
]
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment