Advertisement
OIQ

Untitled

OIQ
Apr 25th, 2020
500
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <set>
  5. #include <cmath>
  6. #include <map>
  7. #include <utility>
  8. #include <fstream>
  9. #include <bitset>
  10. #include <deque>
  11. typedef long long int ll;
  12. #define all(x) (x).begin(),(x).end()
  13. #define endl "\n";
  14. long double pi = 3.14159265358979;
  15. using namespace std;
  16. int inf = 1e12;
  17. ll MOD = 998244353;
  18. void fastIO() {
  19.     ios_base::sync_with_stdio(false);
  20.     cin.tie(0);
  21.     cout.tie(0);
  22. }
  23. vector <vector <int>> gr;
  24. vector <int> dist(int v, int n) {
  25.     vector <int> d(n, -1);
  26.     d[v] = 0;
  27.     deque<int> q;
  28.     q.push_back(v);
  29.     while (!q.empty()) {
  30.         int u = q.front();
  31.         q.pop_front();
  32.         for (int l : gr[u])
  33.             if (d[l] == -1) {
  34.                 d[l] = d[u] + 1;
  35.                 q.push_back(l);
  36.             }
  37.     }
  38.     return d;
  39. }
  40.  
  41. int lmao(vector <int>& a, int d) {
  42.     for (int i = 0; i < a.size(); i++)
  43.         if (a[i] == d)
  44.             return i;
  45. }
  46.  
  47. void solve() {
  48.     int n;
  49.     cin >> n;
  50.     vector <int> a(n);
  51.     for (int i = 0; i < n; i++) cin >> a[i];
  52.     int ind = n - 1;
  53.     int d = 1;
  54.     int l = n;
  55.     while (ind > 0) {
  56.         while (a[ind] != d) ind--;
  57.         for (int i = ind + 1; i < l; i++)
  58.             if (a[i] == a[i - 1] + 1)
  59.                 d++;
  60.             else {
  61.                 cout << "No\n";
  62.                 return;
  63.             }
  64.         l = ind;
  65.         d++;
  66.     }
  67.     cout << "Yes\n";
  68.     return;
  69. }
  70.  
  71. int main() {
  72.     int n;
  73.     cin >> n;
  74.     for (int i = 0; i < n; i++) solve();
  75.    
  76. }
  77.  
  78. //*****************************************************************************************
  79.  
  80. //task 2.3
  81. void solve(int n) {
  82.     cout << n << " " << n - 1 << " " << n - 2;
  83. }
  84.  
  85.  
  86. //task 2.4
  87. int getp(vector <int>& parent, int v) {
  88.     if (parent[v] == v)
  89.         return v;
  90.     else {
  91.         int u = getp(parent, parent[v]);
  92.         parent[v] = u;
  93.         return parent[v];
  94.     }
  95. }
  96.  
  97. void Union(vector <int>& parent, int v, int u) {
  98.     v = getp(parent, v);
  99.     u = getp(parent, u);
  100.     if (v != u)
  101.         parent[v] = u;
  102. }
  103. void solve(int n, int m, int q) {
  104.     vector <vector <int>> a(n, vector <int>(m, 0));
  105.     vector <int> parent(n * m);
  106.     for (int i = 0; i < n; i++)
  107.         for (int j = 0; j < m; j++)
  108.             parent[j + i * m] = j + i * m;
  109.     int res = 0;
  110.     set <int> s;
  111.     for (int l = 0; l < q; l++) {
  112.         int i, j;
  113.         cin >> i >> j;
  114.         if (a[i][j] == 1) continue;
  115.  
  116.         if (a[i - 1][j] == 1) s.insert(parent[j + (i - 1) * m]);
  117.         if (a[i + 1][j] == 1) s.insert(parent[j + (i + 1) * m]);
  118.         if (a[i][j - 1] == 1) s.insert(parent[j - 1 + i * m]);
  119.         if (a[i][j + 1] == 1) s.insert(parent[j + 1 + i * m]);
  120.         if (s.size() == 0) res++;
  121.         else if (s.size() == 2) {
  122.             res--;
  123.             int k = *s.begin();
  124.             s.erase(k);
  125.             Union(parent, k, *s.begin());
  126.         }
  127.         else if (s.size() == 3) {
  128.             int k = *s.begin();
  129.             s.erase(k);
  130.             int d = *s.begin();
  131.             s.erase(d);
  132.             Union(parent, k, d);
  133.             Union(parent, k, *s.begin());
  134.         }
  135.         else if (s.size() == 4) {
  136.             int k = *s.begin();
  137.             s.erase(k);
  138.             int d = *s.begin();
  139.             s.erase(d);
  140.             int p = *s.begin();
  141.             s.erase(p);
  142.             Union(parent, k, d);
  143.             Union(parent, k, p);
  144.             Union(parent, k, *s.begin());
  145.         }
  146.         s.clear();
  147.     }
  148. }
  149. //task 2.1
  150. void solve(vector <vector <pair<int, int>>> gr, int s, int t) {
  151.     vector <int> d(gr.size(), 1e9);
  152.     d[s] = 0;
  153.     deque<int> q;
  154.     q.push_back(s);
  155.     while (!q.empty()) {
  156.         int v = q.front();
  157.         q.pop_front();
  158.         for (pair <int, int> u : gr[v])
  159.             if (d[u.first] > d[v] + u.second) {
  160.                 d[u.first] = d[v] + u.second;
  161.             if (u.second == 0)
  162.                 q.push_front(u.first);
  163.             else q.push_back(u.first);
  164.             }
  165.     }
  166.     cout << d[t];
  167. }
  168. //task 2.2
Advertisement
RAW Paste Data Copied
Advertisement