fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Codechef Draught
  4. //
  5. //  Created by Himanshu on 24/08/21.
  6. //
  7.  
  8. #include <iostream>
  9. #include <vector>
  10. using namespace std;
  11. long long tmp = 0;
  12.  
  13. void dfs(int x, vector<int> graph[], int vis[], int window[], long long &cPath, long long &cNode) {
  14.     tmp++;
  15.     vis[x] = 1;
  16.     // Set tmp = 0, and add the number of paths(tmp) between 
  17.     // two rooms having a window each
  18.     if (window[x] == 1) {
  19.         cNode++;
  20.         cPath += tmp;
  21.         tmp = 0;
  22.     }
  23.     for (int i=0; i<graph[x].size(); i++) {
  24.         int j = graph[x][i];
  25.         if (vis[j] == 0) {
  26.             dfs(j, graph, vis, window, cPath, cNode);
  27.         }
  28.     }
  29.     // Backtracking and removing previously visited
  30.    // node from Rubik's answer 
  31.     tmp--;
  32.     if (tmp < 0) {
  33.         tmp = 0;
  34.     }
  35. }
  36.  
  37. int solve (vector<int> graph[], int window[], int n) {
  38.     int vis[n+1];
  39.     long long ansF = 0, ansR = 0, cPath = 0, cNode = 0;
  40.     for (int i=1; i<=n; i++) {
  41.         vis[i] = 0;
  42.     }
  43.  
  44.     for (int i=1; i<=n; i++) {
  45.         cNode = 0;
  46.         cPath = 0;
  47.         //Performing DFS on each tree, starting from a room 
  48.         // having a window
  49.         if (vis[i] == 0 && window[i] == 1){
  50.             dfs(i, graph, vis, window, cPath, cNode);
  51.             ansF += (cNode*(cNode-1))/2;
  52.             if (cPath > 1) {
  53.                 ansR += cPath;
  54.             }
  55.         }
  56.     }
  57.     cout<<ansF<<" "<<ansR<<endl;
  58.     return 0;
  59. }
  60.  
  61. int main () {
  62.     int n = 0, m = 0;
  63.     cin>>n>>m;
  64.     int window[n+1];
  65.     vector<int> graph[n+1];
  66.     int connect[m+1][2];
  67.  
  68.     for (int i=1; i<=n; i++) {
  69.         cin>>window[i];
  70.     }
  71.     for (int i=1; i<=m; i++) {
  72.         cin>>connect[i][0]>>connect[i][1];
  73.         graph[connect[i][0]].push_back(connect[i][1]);
  74.         graph[connect[i][1]].push_back(connect[i][0]);
  75.     }
  76.  
  77.     solve(graph, window, n);
  78.  
  79.     return 0;
  80. }
Success #stdin #stdout 0.01s 5512KB
comments (?)
stdin
copy 
6 5
1 1 1 1 1 0
1 2
1 6
1 5
2 4
4 3
stdout
copy 
10 5
https://ideone.com/2fZdaE
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!