Posts

Codeforces 510C

#include <iostream> #include <vector> using namespace std; string ret; vector<vector<int>> adj(27); bool dfs(int node,vector<bool>& vu,vector<bool>& path){ if (path[node]) return false; if (vu[node]) return true; vu[node]=true; path[node]=true; ret += 'a'+node; for (auto& i:adj[node]){ if (!dfs(i,vu,path)) return false; } path[node]=false; return true; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<string> v(n); for (int i=0; i<n; ++i) cin >> v[i]; vector<vector<int>> adj(27); for (int i=0; i<n-1; ++i){ string target=v[i],source=v[i+1]; if (target.size() > source.size() and target.substr(source.size()-1) == source){ cout << "Impossible"; return 0; } int idx=0; while (idx < target.size() and target[idx] == source[idx]) idx++; if (i...
Post a Comment
Read more

Online Course in BSU - 770C - Codeforces

#include <bits/stdc++.h> using namespace std; const int BIG_N=100001; deque<int> ans,ret; vector<vector<int>> adj(BIG_N); bool dfs(vector<bool>& look,vector<int>& vu,int node){ if (adj[node].empty()) return true; for (auto& i:adj[node]){ if (vu[i] <= 1){ ans.emplace_back(i); vu[i]++; if (dfs(look,vu,i)) return true; } else if (look[i]) return true; else return false; } return false; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,k; cin >> n >> k; vector<int> v(k); for (int i=0; i<k; ++i) cin >> v[i]; for (int i=1; i<=n; ++i){ int t; cin >> t; for (int j=0; j<t; ++j){ int a; cin >> a; adj[i].emplace_back(a); } } vector<int> vu(n+1); vector<bool> look(n+1); for (auto& i:v){ bool ok=true; if (!vu[i]){ ok=dfs(look,vu,i); ...
Post a Comment
Read more

Kickstart - 2019 - Round A - Parcels

// currently editing #include <bits/stdc++.h> using namespace std; vector<vector<int>> v(250,vector<int>(250,501)) // 250 is max c and r vecto<pair<int,int>> dir{{-1,0},{0,-1},{0,1},{1,0}}; void bfs(int r, int c){ deque<pair<int,int>> q; for (int i=0; i<r; ++i){ for (int j=0; j<c; ++j){ int a; cin >> a; if (a == 1){ q.push_back({i,j}); v[i][j]=0; } } } while (!q.empty()){ auto f=q.front(); int x=f.first,y=f.second; q.pop_front(); for (auto& i:dir){ int nx=i.first+x,ny=y+i.second; if (nx >= 0 and ny >= 0 and nx < r and ny < c){ if (v[nx][ny] > v[x][y]+1){ v[nx][ny]=v[x][y]+1; q.push_back({nx,ny}); } } } } } bool ok(int r, int c, int val){ for (){} } int bs(int r, int c){ int e=r+c,b=0; // Mahattan distance while (b < e){ int mid=b+e; if (ok(r,c,mi...
Post a Comment
Read more