fork download
copy 
  1. // Ziad Sherif Muhammed
  2. // BN: 26    Sec:1
  3.  
  4. #include <bits/stdc++.h>
  5. #include <iostream>
  6.  
  7. using namespace std;
  8.  
  9. #include <string.h>
  10.  
  11. typedef long long ll;
  12. typedef unsigned long long usll;
  13. typedef unsigned long long ull;
  14. typedef long double ld;
  15. typedef vector<pair<ll, ll>> vpll;
  16. typedef vector<pair<int, int>> vpi;
  17. typedef pair<int, int> pi;
  18. typedef vector<int> vi;
  19. typedef vector<long long> vll;
  20. typedef vector<double> vd;
  21. typedef vector<vi> vvi;
  22. typedef vector<vll> vvl;
  23. const ll MOD = 1e19 + 4;
  24.  
  25. typedef vector<string> vs;
  26.  
  27. #define rep(i, v) for (int i = 0; i < v.size(); ++i)
  28. #define print(x) cout << x << endl
  29. #define printV(v) for(int i=0;i<v.size();++i)cout<<v[i]<<" ";
  30. #define readV(v) for(int i=0;i<v.size();++i)cin>>v[i];
  31. #define read2DVector(v) \
  32.     for(int i = 0; i < v.size(); ++i) \
  33.         for(int j = 0; j < v[i].size(); ++j) \
  34.             cin >> v[i][j];
  35. #define en cout<<'\n';
  36. #define fast ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
  37. #define OOLL LLONG_MAX
  38. #define OO   INT_MAX
  39. #define M_PI 3.14159265358979323846
  40. ll n, t, c;
  41. string S;
  42.  
  43. ll gcd(ll a, ll b) {
  44.     if (b == 0)
  45.         return a;
  46.     return gcd(b, a % b);
  47. }
  48.  
  49. ll lcm(ll a, ll b) {
  50.     return (a / gcd(a, b)) * b;
  51. }
  52.  
  53. // compute sum of vector
  54.  
  55. usll factorial(usll n) {
  56.     if (n == 0)
  57.         return 1;
  58.     c = n;
  59.     for (int i = n - 1; i > 1; i--)
  60.         c *= i;
  61.     return c;
  62. }
  63.  
  64. bool cmp(pair<ll, ll> &a,
  65.          pair<ll, ll> &b) {
  66.     return a.second > b.second;
  67. }
  68.  
  69. bool sortByCond(const pair<ll, ll> &a, const pair<ll, ll> &b) {
  70.     if (a.first != b.first)
  71.         return (a.first < b.first);
  72.     else
  73.         return a.second > b.second;
  74. }
  75.  
  76. bool sortStrPair(pair<string, pair<ll, ll>> &a, pair<string, pair<ll, ll>> &b) {
  77.     if (a.second.first != b.second.first)
  78.         return (a.second.first < b.second.first);
  79.     else
  80.         return a.second.second > b.second.second;
  81. }
  82.  
  83. bool sortChar(pair<char, ll> &a, pair<char, ll> &b) {
  84.     if (a.second != b.second)
  85.         return (a.second > b.second);
  86.     else
  87.         return a.first > b.first;
  88. }
  89.  
  90. bool newSort(pair<ll, string> &a, pair<ll, string> &b) {
  91.     if (a.second != b.second)
  92.         return (a.second > b.second);
  93.     else
  94.         return a.first > b.first;
  95. //    if (a.first != b.first)
  96. //        return (a.first < b.first);
  97. //    else
  98. //        return a.second > b.second;
  99. }
  100.  
  101. bool primeTest(ll n) {
  102.  
  103.     bool flag = true;
  104.     for (int i = 2; i * i <= n; i++) {
  105.         if (n % i == 0) {
  106.             flag = false;
  107.             break;
  108.         }
  109.     }
  110.     if (n <= 1)
  111.         flag = false;
  112.     if (flag == 1)
  113.         return true;
  114.     return false;
  115. }
  116.  
  117. ll nearestPrimeNumber(ll n) {
  118.     if (n & 1)
  119.         n -= 2;
  120.     else
  121.         n--;
  122.     int i, j;
  123.     for (i = n; i >= 2; i -= 2) {
  124.         if (i % 2 == 0)
  125.             continue;
  126.         for (j = 3; j * j <= i; j += 2) {
  127.             if (i % j == 0)
  128.                 break;
  129.         }
  130.         if (j * j > i)
  131.             return i;
  132.     }
  133.     return 2;
  134. }
  135.  
  136. void adjacentList(vector<vector<pair<int, int>>> adjList) {
  137.     for (int i = 0; i < adjList.size(); ++i) {
  138.         cout << "Node " << i + 1 << " -->";
  139.         for (int j = 0; j < adjList[i].size(); ++j) {
  140.             cout << "{ " << adjList[i][j].first << " , " << adjList[i][j].second << " }";
  141.         }
  142.         cout << '\n';
  143.     }
  144. }
  145.  
  146. vector<bool> isVisited(10000001, false);
  147. vector<ll> cated(1000001);
  148.  
  149. void dfs(vector<vector<int>> &graph, int node) {
  150.     cout << node << '\n';
  151.     isVisited[node] = true;
  152.     for (auto child: graph[node]) {
  153.         if (!isVisited[child])
  154.             dfs(graph, child);
  155.     }
  156. }
  157.  
  158. void bfs(vector<vector<int>> graph, int node) {
  159.     queue<int> nextToVisit;
  160.     nextToVisit.push(node);
  161.     while (!nextToVisit.empty()) {
  162.         int current = nextToVisit.front();
  163.         isVisited[current] = true;
  164.         nextToVisit.pop();
  165.         cout << current << '\n';
  166.         for (auto child: graph[current]) {
  167.             if (!isVisited[child]) {
  168.                 isVisited[child] = true;
  169.                 nextToVisit.push(child);
  170.             }
  171.         }
  172.     }
  173. }
  174.  
  175. void dijk(int source, vector<vector<pair<int, int>>> &graph) {
  176.  
  177.     int n = graph.size();
  178.     vector<int> dist(n, OO), pre(n, -1);
  179.     // cost, node
  180.     priority_queue<pair<int, int>> nextToVisit;
  181.  
  182.  
  183.     dist[source] = 0;
  184.     pre[source] = source;
  185.     nextToVisit.push({0, source});
  186.  
  187.  
  188.     while (!nextToVisit.empty()) {
  189.         int u = nextToVisit.top().second;
  190.         nextToVisit.pop();
  191.         if (isVisited[u])
  192.             continue;
  193.         isVisited[u] = true;
  194.         for (auto e: graph[u]) {
  195.             int v = e.first;
  196.             int c = e.second;
  197.             if (dist[u] + c < dist[v]) {
  198.                 dist[v] = dist[u] + c;
  199.                 pre[v] = u;
  200.                 nextToVisit.push({-dist[v], v});
  201.             }
  202.         }
  203.     }
  204.     for (int i = 1; i < n; ++i) {
  205.         cout << i << ": " << dist[i] << ": " << pre[i] << "\n";
  206.     }
  207.  
  208. }
  209.  
  210.  
  211. int ans = 0, m;
  212.  
  213. void dfsSolve(vector<vector<ll>> &graph, ll node, ll cnt) {
  214.     //    cout<<"CNT:"<<cnt<<" Node:"<<node<<'\n';
  215.     if (cnt > m)
  216.         return;
  217.     isVisited[node] = true;
  218.     bool flag = false;
  219.     for (auto child: graph[node]) {
  220.         if (!isVisited[child]) {
  221.             flag = true;
  222.             isVisited[child] = 1;
  223.             if (cated[child]) {
  224.                 dfsSolve(graph, child, cnt + 1);
  225.             } else
  226.                 dfsSolve(graph, child, 0);
  227.         }
  228.     }
  229.     if (!flag)
  230.         ans++;
  231. }
  232.  
  233. //string toLowerCase(string S) {
  234. //    // get unique of char in order
  235. //    //    S.erase(unique(S.begin(), S.end()), S.end());
  236. //    transform(S.begin(), S.end(), S.begin(), [](char c) {
  237. //        return tolower(c);
  238. //    });
  239. //}
  240.  
  241. ll fasPow(ll b, ll p) {
  242.     if (b == 1 || p == 0) {
  243.         return 1;
  244.     }
  245.     ll hp = fasPow(b, p / 2);
  246.     ll res = (hp % MOD * hp % MOD) % MOD;
  247.     if (p & 1) {
  248.         res = (res * b) % MOD;
  249.     }
  250.     return res;
  251. }
  252.  
  253. bool inRange(unsigned low, unsigned high, unsigned x) {
  254.     return (low <= x && x <= high);
  255. }
  256.  
  257. int intersect(unsigned row, unsigned column) {
  258.     if (column >= 4 && column <= 5 && (row <= 5 && row >= 4)) {
  259.         return 5;
  260.     } else if (column >= 3 && column <= 6 && (row >= 3 && row <= 6)) {
  261.         return 4;
  262.     } else if (column >= 2 && column <= 7 && (row >= 2 && row <= 7)) {
  263.  
  264.         return 3;
  265.     } else if (column >= 1 && column <= 8 && (row >= 1 && row <= 8)) {
  266.         return 2;
  267.     } else if (column >= 0 && column <= 9 && (row >= 0 && row <= 9)) {
  268.         return 1;
  269.     } else {
  270.         return 0;
  271.     }
  272. }
  273.  
  274.  
  275. void RREQ(vector<vector<ll>> &graph, vll &path, ll current, ll destination, ll destGraph) {
  276.     // print graph
  277.     ll sz = graph.size();
  278. //    cout << "sz" << sz << endl;
  279. //    en;
  280. //    for (int i = 1; i < sz; ++i) {
  281. //        int row = graph[i].size();
  282. //        cout << "Vertex: " << i << " To: ";
  283. //        for (int j = 0; j < row; ++j) {
  284. //            cout << graph[i][j] << " ";
  285. //        }
  286. //        en;
  287. //    }
  288. //    print("======================");
  289. //    cout << "Current Node: " << current << endl;
  290.  
  291.     if (current == destination) {
  292.         path.push_back(current);
  293.         return;
  294.     }
  295.  
  296.     queue<ll> queue;
  297.     queue.push(current);
  298.  
  299.     vector<bool> visited(sz, false);
  300.     visited[current] = true;
  301.  
  302.     vll parent(sz, -1);
  303.  
  304.     while (!queue.empty()) {
  305.         ll node = queue.front();
  306.         queue.pop();
  307. //        cout << "Visiting Node: " << node << endl;
  308.  
  309.         if (node == destination)
  310.             break;
  311.  
  312.  
  313.         priority_queue<ll, vll> pq;
  314.         for (ll neighbor: graph[node]) {
  315.             if (!visited[neighbor] && neighbor != destGraph) {
  316.                 pq.push(neighbor);
  317.             }
  318.         }
  319.  
  320.         while (!pq.empty()) {
  321.             ll neighbor = pq.top();
  322.             pq.pop();
  323.  
  324.             visited[neighbor] = true;
  325.             parent[neighbor] = node;
  326.             queue.push(neighbor);
  327. //            cout << "Pushing Neighbor: " << neighbor << " to the queue" << endl;
  328.  
  329.         }
  330.  
  331.  
  332.     }
  333.  
  334.     ll currentNode = destination;
  335.     while (currentNode != -1) {
  336.         path.push_back(currentNode);
  337.         currentNode = parent[currentNode];
  338.     }
  339.  
  340.     reverse(path.begin(), path.end());
  341.  
  342.  
  343.     //        sort(graph[node].begin(), graph[node].end());
  344. //
  345. //        for (int neighbor: graph[node]) {
  346. //            if (visited[neighbor] || neighbor == destGraph)
  347. //                continue;
  348. //
  349. //            visited[neighbor] = true;
  350. //            parent[neighbor] = node;
  351. //            queue.push(neighbor);
  352. //
  353. //        }
  354. }
  355.  
  356. void solve() {
  357.     cin >> n;
  358.  
  359. }
  360.  
  361. int main() {
  362.     fast;
  363.     //    freopen("task.in","r",stdin);
  364. //    t = 1;
  365. //    cin >> t;
  366. //    while (t--)
  367. //        solve();
  368.  
  369.  
  370.     //    int n; //n==> # of  nodes , m= # of edges
  371.     cin >> n >> m;
  372.     vector<vector<ll>> adj(n + 1);
  373.     //    for (int i = 1; i <= n; ++i)
  374.     //        cin >> cated[i];
  375.     //
  376.  
  377.     //    4 5
  378.     //    1 2 6
  379.     //    1 3 2
  380.     //    3 4 5
  381.     //    3 2 3
  382.     //    2 4 1
  383.     ll src, dst, c, k;
  384.     for (int i = 0; i < m; ++i) {
  385.         cin >> k;
  386.         cin >> c;
  387. //      adj[u].push_back({i, c}); // directed graph
  388.         adj[c].push_back(k); // undirected graph
  389.         adj[k].push_back(c);  // undirected graph
  390.     }
  391.     cin >> src >> dst;
  392.  
  393.     for (int i = 1; i <= n; ++i) {
  394.         vll path;
  395.  
  396.         if (i == dst) {
  397.             print(-1);
  398.         } else {
  399.             RREQ(adj, path, src, i, dst);
  400.             if (!path.empty() && std::find(path.begin(), path.end(), src) != path.end()) {
  401.                 for (int node: path) {
  402.                     cout << node << " ";
  403.                 }
  404.                 en;
  405.             } else {
  406.                 print(-1);
  407.             }
  408.         }
  409.     }
  410. //    adj[u].push_back(v);
  411. //    adj[v].push_back(u);
  412. //        dijk(1, adj);
  413.     //    dfsSolve(adj, 1, cated[1]);
  414.     //    cout << ans;
  415.     //    dfs(adj, 0);
  416.     return 0;
  417. }
  418.  
Success #stdin #stdout 0.01s 12060KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5nADXA
language:
C++14 (gcc 8.3)
created:
21 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!