fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <unordered_map>
  5. #include <set>
  6. #include <algorithm>
  7. #include <cmath>
  8. #include <fstream>
  9. #include <ctime>
  10. #include <stdio.h>      /* printf */
  11. #include <stdlib.h>
  12. #include <queue>
  13.  
  14. #ifdef SHOW_DEBUG
  15. #define dbg(a, ...) printf("DEBUG: " a "\n", ##__VA_ARGS__)
  16. #else
  17. #define dbg(...) ((void*)(0))
  18. #endif
  19.  
  20. using namespace std;
  21. typedef long long ll;
  22. template<typename A, typename B>
  23. using hmap = unordered_map<A, B>;
  24. typedef tuple<int, int> ii;
  25. typedef tuple<ll, ll> lii;
  26. #define PI 3.14159265358979323846
  27. #define inf 0x3f3f3f3f
  28. #define infl 0x3f3f3f3f3f3f3f3fL
  29.  
  30. void step(vector<vector<ll>>& edges, set<ll> nodes, vector<vector<ll>>& dist, ll running_dist){
  31.     set<ll> new_nodes;
  32.     ll new_dist = running_dist + 1;
  33.     for (ll node : nodes){
  34.         for (ll j = 0; j < edges[node].size(); j++){
  35.             ll p = (new_dist) % 2;
  36.             ll neighbor = edges[node][j];
  37.             if (dist[neighbor][p] == -1 || new_dist < dist[neighbor][p] ){
  38.                 dist[neighbor][p] = new_dist;
  39.                 new_nodes.insert(neighbor);
  40.             }
  41.         }
  42.     }
  43.     if (!new_nodes.empty()){
  44.         step(edges, new_nodes, dist, running_dist + 1);
  45.     }
  46. }
  47.  
  48. void bfs(vector<vector<ll>>& edges, ll start, vector<vector<ll>>& dist){
  49.     set<ll> nodes;
  50.     nodes.insert(start);
  51.     step(edges, nodes, dist, 0);
  52. }
  53.  
  54. int main() {
  55.     ios::sync_with_stdio(false);
  56.     cin.tie(nullptr);
  57.  
  58.     ll tt;
  59.     cin >> tt;
  60.     for (ll t = 0; t < tt; t++){
  61.         ll n, m, l;
  62.         cin >> n >> m >> l;
  63.         vector<ll> A(l);
  64.         for (ll i = 0; i < l; i++){
  65.             cin >> A[i];
  66.         }
  67.         vector<vector<ll>> edges(n);
  68.         for (ll i = 0; i < m; i++){
  69.             ll u, v;
  70.             cin >> u >> v;
  71.             u--;
  72.             v--;
  73.             edges[u].push_back(v);
  74.             edges[v].push_back(u);
  75.         }
  76.         for (ll i = 0; i < n; i++){
  77.             sort(edges[i].begin(), edges[i].end());
  78.         }
  79.  
  80.         vector<vector<ll>> dist(n, vector<ll>(2, -1));
  81.         dist[0][0] = 0;
  82.         dist[0][1] = -1;
  83.         bfs(edges, 0, dist);
  84.  
  85.         sort(A.begin(), A.end());
  86.         ll min_odd = -1;
  87.         for (ll i = 0; i < A.size(); i++){
  88.             if (A[i] % 2 == 1){
  89.                 min_odd = A[i];
  90.                 break;
  91.             }
  92.         }
  93.         ll sum = 0;
  94.         for (ll i = 0; i < A.size(); i++){
  95.             sum += A[i];
  96.         }
  97.         ll even_sum = -1;
  98.         ll odd_sum = -1;
  99.         if (sum % 2 == 0){
  100.             even_sum = sum;
  101.             if (min_odd != -1){
  102.                 odd_sum = sum - min_odd;
  103.             }
  104.         } else {
  105.             odd_sum = sum;
  106.             if (min_odd != -1){
  107.                 even_sum = sum - min_odd;
  108.             }
  109.         }
  110.  
  111.         vector<ll> ans(n);
  112.         for (ll i = 0; i < ans.size(); i++){
  113.             if ((dist[i][0] > -1 && dist[i][0] <= even_sum) || (dist[i][1] > -1 && dist[i][1] <= odd_sum)){
  114.                 ans[i] = 1;
  115.             }
  116.         }
  117.         for (ll i = 0; i < ans.size(); i++){
  118.             cout << ans[i];
  119.         }
  120.         cout << endl;
  121.  
  122.     }
  123.  
  124.     return 0;
  125. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
3
6 5 2
2 3
1 2
2 3
3 4
4 5
5 6
5 5 1
5
1 2
2 3
3 4
4 5
3 5
5 4 3
100 200 300
1 2
1 3
1 4
2 5
stdout
copy 
111101
11111
10001
https://ideone.com/G9oDPJ
language:
C++14 (gcc 8.3)
created:
8 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!