제출 #1016454

#제출 시각아이디문제언어결과실행 시간메모리
1016454asdfgraceStranded Far From Home (BOI22_island)C++17
100 / 100
143 ms36548 KiB
#include <bits/stdc++.h> using namespace std; #define dbg(x) //x #define prt(x) dbg(cerr << x) #define pv(x) dbg(cerr << #x << " = " << x << '\n') #define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n') #define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");) #define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << " "); prt("}\n");) #define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n')); #define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n')); int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<int> ord(n); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&] (int x, int y) { return a[x] < a[y]; }); vector<int> at(n); for (int i = 0; i < n; i++) { at[ord[i]] = i; } vector<vector<int>> edges(n); for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; x--; y--; x = at[x]; y = at[y]; if (x > y) swap(x, y); edges[y].push_back(x); } vector<int> g(n), sz(n, 1); iota(g.begin(), g.end(), 0); vector<vector<int>> in(n); vector<long long> sum(n); for (int i = 0; i < n; i++) { in[i].push_back(i); sum[i] = a[ord[i]]; } function<int(int)> rep = [&] (int node) { while (node != g[node]) node = g[g[node]]; return node; }; function<void(int, int)> merge = [&] (int x, int y) { x = rep(x); y = rep(y); if (x == y) return; if (sz[y] > sz[x]) swap(x, y); g[y] = x; sz[x] += sz[y]; sum[x] += sum[y]; for (auto i : in[y]) { in[x].push_back(i); } in[y].clear(); }; for (int i = 0; i < n; i++) { sort(edges[i].begin(), edges[i].end(), [&] (int x, int y) { return sum[rep(x)] < sum[rep(y)]; }); for (auto j : edges[i]) { int ri = rep(i), rj = rep(j); if (ri == rj) continue; if (a[ord[i]] > sum[rj]) { in[rj].clear(); } merge(ri, rj); } } vector<bool> ok(n, false); for (int i = 0; i < n; i++) { if (sz[i] == n) { for (auto j : in[i]) { ok[ord[j]] = true; } break; } } for (int i = 0; i < n; i++) { cout << (ok[i] ? '1' : '0'); } cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...