fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cstdlib>
  6.  
  7. using namespace std;
  8. inline void scan(int *a)
  9. {
  10.     register char c = 0;
  11.     while(c<33)
  12.         c = getchar_unlocked();
  13.     *a = 0;
  14.     while(c > 33)
  15.     {
  16.         *a=*a*10+c-'0';
  17.         c= getchar_unlocked();
  18.     }
  19. }
  20.  
  21.  
  22. int arr[50003] = {0} , reachable[50003] = {0};
  23. int pls = 0;
  24. long long int tomul = 0 , ans = 0;
  25. vector < vector<int> >  graph;
  26. //vector<int> location ;
  27. void dfs(int start_vertex , vector<int> &visited )
  28. {
  29.     visited[start_vertex] = 1;
  30.     if(arr[start_vertex]==1)
  31.         tomul++;
  32.     //cout<<tomul<<endl;
  33.     //newly.push_back(start_vertex);
  34.     for(auto it:graph[start_vertex])
  35.     {
  36.         if(!visited[it])
  37.         {
  38.             //location.push_back(it);
  39.             pls++;
  40.             if(arr[it] == 1)
  41.             {
  42.                  ans += pls;
  43.                  pls =  0;
  44.             }
  45.  
  46.             /*for(auto k: location)
  47.                 cout<<k<<" ";
  48.             cout<<endl;*/
  49.             dfs(it , visited);
  50.             pls--;
  51.             if(pls<0)
  52.                 pls = 0;
  53.         //    location.pop_back();
  54.         }
  55.  
  56.     }
  57. }
  58.  
  59. void paths(int start_vertex , int tot)
  60. {
  61.     long long int second = 0;
  62.     vector <int> visited(tot+1 , 0);
  63.     pls = 1;
  64.   //  location.push_back(start_vertex);
  65.     tomul = 0;
  66.     dfs(start_vertex , visited);
  67.     second += (tomul*(tomul-1))/2;
  68. //    cout<<tomul<<endl;
  69.     //newly.clear();
  70.     //location.clear();
  71.     for(int i = 1; i <= tot; i++)
  72.     {
  73.         if(visited[i] == 0)
  74.         {
  75.                 //cout<<"Its "<<i<<endl;
  76.             if(arr[i] == 1)
  77.             {
  78.                 //cout<<"hi";
  79.       //          location.push_back(i);
  80.                 pls = 1;
  81.                 tomul = 0;
  82.                 dfs(i , visited);
  83.  
  84.                 second += (tomul*(tomul-1))/2;
  85.                 //newly.clear();
  86.         //        location.clear();
  87.             }
  88.         }
  89.     }
  90.     printf("%lld %lld\n" , second,ans);
  91. }
  92. int main()
  93. {
  94.     int n ,m, from,to;
  95.  
  96.     scan(&n);
  97.     scan(&m);
  98.     vector <int> empty_vector;
  99.     //vector <int> colour(n+1 , 0);
  100.     for(int i = 0; i <= n ; i++)
  101.     {
  102.         graph.push_back(empty_vector);
  103.     }
  104.     int flag = 0 , start = 1;
  105.     for(int i =1;i <= n; i++)
  106.     {
  107.         scan(&arr[i]);
  108.         if(arr[i] == 1)
  109.         {
  110.     //        ans++;
  111.             if(flag == 0)
  112.             {
  113.                 flag = 1;
  114.                 start = i;
  115.             }
  116.         }
  117.     }
  118.     while(m--)
  119.     {
  120.         scan(&from);
  121.         scan(&to);
  122.         graph[from].push_back(to);
  123.         graph[to].push_back(from);
  124.     }
  125.     if(m == 0)
  126.     {
  127.         cout<<"0 0"<<endl;
  128.         return 0;
  129.     }
  130.  
  131.     paths(start,n);
  132.     return 0;
  133. }
Success #stdin #stdout 0s 3868KB
comments (?)
stdin
copy 
50 49
1 0 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 0 0 1 1 1 0 
40 48
46 19
38 4
44 34
10 35
42 44
7 23
38 24
12 1
15 31
29 22
48 39
2 42
25 13
9 18
41 50
17 36
19 6
41 14
39 3
48 31
48 6
5 35
32 18
36 46
49 16
18 46
6 21
37 30
34 47
50 26
47 18
14 17
30 12
6 27
34 1
20 27
11 18
31 35
13 48
14 23
29 45
1 8
13 38
33 50
17 45
38 16
43 27
28 26
stdout
copy 
406 37
https://ideone.com/Vl6ch6
language:
C++14 (gcc 8.3)
created:
9 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!