999ms

Untitled

Jan 29th, 2020
181
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.10 KB | None | 0 0
  1.     #include <bits/stdc++.h>
  2.     #define all(x) (x).begin(),(x).end()
  3.      
  4.     using namespace std;
  5.     using ll = long long;
  6.      
  7.     const int N = 100100;
  8.      
  9.     struct Edge {
  10.         int to, type;  
  11.     };
  12.      
  13.     int type[N];
  14.     const int A = 1;
  15.     const int B = 2;
  16.      
  17.     vector<Edge> g[N];
  18.     int color[N];
  19.      
  20.     void PaintDfs(int from, int clr) {
  21.         color[from] = clr;
  22.         for (auto& [to, tp] : g[from]) {
  23.             if (!color[to]) {
  24.                 PaintDfs(to, clr);
  25.             }
  26.         }
  27.     }
  28.      
  29.     void Dfs2(int from) {
  30.         for (auto& [to, tp] : g[from]) {
  31.             if (type[from] == 0 && type[to] == 0) {
  32.                 type[from] = tp;
  33.                 type[to] = tp;
  34.                 Dfs2(to);
  35.             } else if (type[to] == 0) {
  36.                 Dfs2(to);
  37.             }
  38.         }
  39.     }
  40.      
  41.     int main() {
  42.         ios_base::sync_with_stdio(false);
  43.         cin.tie(nullptr);
  44.         cout.tie(nullptr);
  45.         int n, a, b;
  46.         cin >> n >> a >> b;
  47.         vector<int> p(n, 0);
  48.         set<int> values;
  49.         for (int i = 0; i < n; i++) {
  50.             cin >> p[i];
  51.             values.insert(p[i]);
  52.         }  
  53.         int itr = 0;
  54.         map<int,int> mp, rev;
  55.         for (auto& val : values) {
  56.             mp[val] = itr;
  57.             rev[itr++] = val;
  58.         }
  59.         set<pair<int,int>> st;
  60.         map<int, int> get;
  61.         for (int i = 0; i < n; i++) {
  62.             if (!values.count(a - p[i]) && !values.count(b - p[i])) {
  63.                 cout << "NO\n";
  64.                 return 0;
  65.             }
  66.             if (values.count(a - p[i])) {
  67.                 g[mp[p[i]]].push_back(Edge{mp[a - p[i]], A});
  68.             }
  69.             if (values.count(b - p[i])) {
  70.                 g[mp[p[i]]].push_back(Edge{mp[b - p[i]], B});
  71.             }
  72.             st.insert({g[mp[p[i]]].size(), mp[p[i]]});
  73.             p[i] = mp[p[i]];   
  74.             get[p[i]] = g[p[i]].size();
  75.             st.insert({get[p[i]], p[i]});
  76.         }
  77.        
  78.         while (st.size() && st.begin()->first <= 1) {
  79.             auto [q, from] = *st.begin();
  80.             st.erase(st.begin());
  81.             if (type[from]) {
  82.                 continue;
  83.             }
  84.             for (auto [to, tp] : g[from]) {
  85.                 if (type[to] == 0) {
  86.                     type[from] = tp;
  87.                     type[to] = tp;
  88.                     st.erase({get[to], to});
  89.                     for (auto& [to2, tp2] : g[to]) {
  90.                         st.insert({--get[to2], to2});
  91.                     }
  92.                 }
  93.             }
  94.         }
  95.        
  96.         int clr = 1;
  97.         for (int i = 0; i < n; i++) {
  98.             if (type[i] == 0 && color[i] == 0) {
  99.                 PaintDfs(i, clr++);
  100.             }
  101.         }
  102.        
  103.         vector<vector<int>> vertexes(clr);
  104.         for (int i = 0; i < n; i++) {
  105.             if (type[i] == 0) {
  106.                 vertexes[color[i]].push_back(i);
  107.             }
  108.         }
  109.        
  110.         for (int i = 1; i < clr; i++) {
  111.             bool isChain = false;
  112.             int start = -1;
  113.             for (int vertex : vertexes[i]) {
  114.                 for (auto& [to, tp] : g[vertex]) {
  115.                     if (to == vertex) {
  116.                         isChain = true;
  117.                         start = vertex;
  118.                     }
  119.                 }
  120.             }
  121.             if (isChain) {
  122.                 Dfs2(start);
  123.             } else if (vertexes[i].size() & 1) {
  124.                 cout << "NO\n";
  125.                 return 0;
  126.             } else {
  127.                 Dfs2(vertexes[i][0]);
  128.             }
  129.         }
  130.         cout << "YES" << endl;
  131.         for (int i = 0; i < n; i++) {
  132.             cout << type[p[i]] - 1 << " ";
  133.         }
  134.         cout << endl;
  135.     }
Add Comment
Please, Sign In to add comment