Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Problem: D. D/D/D
- // Contest: Codeforces - Codeforces Round 1025 (Div. 2)
- // URL: https://codeforces.com/contest/2109/problem/D
- // Memory Limit: 512 MB
- // Time Limit: 2000 ms
- //
- // Powered by CP Editor (https://cpeditor.org)
- #include <assert.h>
- #include <bits/stdc++.h>
- using namespace std;
- #ifndef __DEBUG__
- #define dbg(...) 42
- #endif
- template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
- namespace rngs = std::ranges;
- using ll = long long;
- using a2l = array<ll, 2>;
- using pll = pair<ll, ll>;
- using vl = vector<ll>;
- void solve(ll t)
- {
- stringstream ts;
- ll n, m, l;
- cin >> n >> m >> l;
- ts << n << ',' << m << ',' << l;
- vl as(l);
- vl odds, evens;
- for (auto &x : as) {
- cin >> x;
- ts << '/' << x;
- (x % 2 ? odds : evens).push_back(x);
- }
- rngs::sort(odds), rngs::sort(evens);
- ts << ':';
- vector<vl> g(n + 1);
- vector<vl> dist(2, vl(n + 1, LLONG_MAX / 2));
- for (ll i = 0, u, v; i < m; ++i) {
- cin >> u >> v;
- ts << '<' << u << ',' << v << '>';
- g[u].push_back(v), g[v].push_back(u);
- }
- /*
- if (t == 73) {
- cout << ts.str() << '\n';
- return;
- }
- */
- dist[0][1] = 0;
- queue<a2l> q;
- q.push({1, 0});
- while (!q.empty()) {
- auto [u, step] = q.front();
- q.pop();
- for (auto v : g[u]) {
- if (dist[1 - step][v] > dist[step][u] + 1) {
- dist[1 - step][v] = dist[step][u] + 1;
- q.push({v, 1 - step});
- }
- }
- }
- ll ec = std::accumulate(evens.begin(), evens.end(), 0ll);
- ll oc = std::accumulate(odds.begin(), odds.end(), 0ll);
- ll even_avail = ec + (oc % 2 == 0 ? oc : oc - odds[0]);
- ll odd_avail = LLONG_MIN / 2;
- if (oc != 0)
- odd_avail = (oc % 2 == 0 ? oc - odds[0] : oc) + ec;
- dbg(dist);
- string s(n, ' ');
- for (ll i = 1; i <= n; ++i) {
- s[i - 1] = ll(dist[0][i] <= even_avail || dist[1][i] <= odd_avail) + '0';
- }
- cout << s << '\n';
- }
- int main(int argc, char **argv)
- {
- std::ios::sync_with_stdio(false);
- std::cin.tie(nullptr);
- ll t;
- cin >> t;
- ll ot = t;
- while (t--)
- solve(ot - t);
- return 0;
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
