Submission #1264396

#TimeUsernameProblemLanguageResultExecution timeMemory
1264396hahahoang132Stranded Far From Home (BOI22_island)C++20
100 / 100
278 ms79844 KiB
//#pragma GCC optimize("O2") #include<bits/stdc++.h> using namespace std; #define ll long long #define ld long double const ll N = 1e6 + 5; const ll inf = LLONG_MAX/5; const ll mod = 998244353; #define bit(x,y) ((x >> y) & 1LL) ll b[N]; vector<ll> a[N]; ll p[N],sz[N]; vector<ll> sus[N]; ll ans[N],id[N]; ll cmp(ll x, ll y) { return b[x] < b[y]; } ll fp(ll x) { if(p[x] == 0) return x; else { p[x] = fp(p[x]); return p[x]; } } void hop(ll x, ll y) { x = fp(x); y = fp(y); if(x == y) return; if(sus[x].size() < sus[y].size()) swap(x,y); p[y] = x; sz[x] += sz[y]; while(sus[y].size() > 0) { sus[x].push_back(sus[y].back()); sus[y].pop_back(); } } int main() { ll n,m; cin >> n >> m; ll i,j; vector<ll> c; for(i = 1;i <= n;i++) { p[i] = 0; c.push_back(i); cin >> b[i]; sz[i] = b[i]; sus[i].push_back(i); } for(i = 1;i <= m;i++) { ll x,y; cin >> x >> y; a[x].push_back(y); a[y].push_back(x); } sort(c.begin(),c.end(),cmp); for(i = 0;i < c.size();i++) { id[c[i]] = i; } for(auto x : c) { for(auto y : a[x]) { if(id[y] > id[x]) continue; if(sz[fp(y)] < b[x]) { sus[fp(y)].clear(); } hop(x,y); } } ll r = fp(1); for(auto x : sus[r]) ans[x] = 1; for(i = 1;i <= n;i++) cout << ans[i]; }
#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...