Submission #963382

#TimeUsernameProblemLanguageResultExecution timeMemory
963382Spade1Stranded Far From Home (BOI22_island)C++14
100 / 100
96 ms17420 KiB
#pragma once #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double db; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<ld, ld> pld; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ld> vld; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<pld> vpld; typedef vector<vi> vvi; typedef tuple<ll, ll, ll> t3; typedef tuple<ll, ll, ll, ll> t4; template<typename T> using pq = priority_queue<T>; template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>; #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define st first #define nd second #define lb lower_bound #define ub upper_bound #define all(x) (x).begin(), (x).end() #define ins insert #define int ll template<typename T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int MOD = 1e9 + 7; const int INF = 0x3fffffff; const ll LINF = 0x1fffffffffffffff; const char nl = '\n'; const int MX = 2e5 + 3; ll s[MX], ans[MX], sz[MX], rep[MX]; vector<t3> edges; int f(int i) { if (i == rep[i]) return i; int par = f(rep[i]); if (ans[rep[i]] == 0) ans[i] = 0; return rep[i] = par; } void solve() { int n, m; cin >> n >> m; int mx = 0; for (int i = 1; i <= n; ++i) { cin >> s[i]; sz[i] = s[i]; ans[i] = 1; rep[i] = i; } for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; edges.pb({max(s[u], s[v]), u, v}); } sort(all(edges)); for (auto [M, u, v] : edges) { int fu = f(u), fv = f(v); if (fu == fv) continue; if (s[fu] < s[fv]) swap(fu, fv); if (s[fu] > sz[fv]) ans[fv] = 0; sz[fu] += sz[fv]; rep[fv] = rep[fu]; } for (int i = 1; i <= n; ++i) f(i), cout << ans[i]; cout << nl; } signed main(int argc, char* argv[]) { ios_base::sync_with_stdio(0); cin.tie(NULL); int t = 1; // cin >> t; while (t--) { solve(); } return 0; }

Compilation message (stderr)

island.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
island.cpp: In function 'void solve()':
island.cpp:70:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |   for (auto [M, u, v] : edges) {
      |             ^
island.cpp:58:7: warning: unused variable 'mx' [-Wunused-variable]
   58 |   int mx = 0;
      |       ^~
island.cpp: At global scope:
island.cpp:82:8: warning: first argument of 'int main(ll, char**)' should be 'int' [-Wmain]
   82 | signed main(int argc, char* argv[]) {
      |        ^~~~
#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...