Submission #586742

#TimeUsernameProblemLanguageResultExecution timeMemory
586742nots0fastStranded Far From Home (BOI22_island)C++17
10 / 100
1073 ms94984 KiB
#include <bits/stdc++.h> using namespace std; #define mp(a,b) make_pair(a,b) #define mt make_tuple #define ff first #define setp setprecision(12)<<fixed #define ss second #define fori(v) for(int i=0; i<v; i++) #define forj(v) for(int j=0; j<v; j++) #define fork(v) for(int k=0; k<v; k++) #define forl(v) for(int l=0; l<v; l++) #define fort(v) for(int t=0; t<v; t++) #define forz(v) for(int z=0; z<v; z++) #define ll long long #define lll __int128 #define ld long double #define pb(a) push_back(a) // #define cout out // #define cin in ll inf = pow(10,18); ll modulo = 1000000007; double eps = 1e-10; ifstream in; ofstream out; #define MAX 200'200 ll arr[MAX]; namespace dsu{ int aid[MAX]; vector<int> dsu[MAX]; vector<ll> good[MAX]; set<pair<ll, ll> > edg[MAX]; // which node, what is the value ll s[MAX]; void ini(int n){ fori(n) aid[i] = i, dsu[i].clear(), dsu[i].push_back(i), good[i].pb(i), s[i] = arr[i]; } ll join(int a,int b){ // 1 - if joined, 0 - if they were already joined int aid1 = aid[a], aid2 = aid[b]; if(aid1==aid2) return -1; if(dsu[aid2].size() > dsu[aid1].size()) swap(aid1,aid2); { if(good[aid1].size() < good[aid2].size()){ swap(good[aid1], good[aid2]); } for(auto& el : good[aid2]){ good[aid1].pb(el); } } { if(edg[aid1].size() < edg[aid2].size()){ swap(edg[aid1], edg[aid2]); } for(auto& el : edg[aid2]){ edg[aid1].insert(el); } } for(auto hd : dsu[aid2]){ aid[hd] = aid1; dsu[aid1].push_back(hd); } dsu[aid2].clear(); s[aid1]+=s[aid2]; return aid1; } }; using namespace dsu; void deal(){ ll n, m; cin>>n>>m; fori(n){ cin>>arr[i]; } ini(n); fori(m){ ll ai, bi; cin>>ai>>bi; --ai, --bi; edg[ai].insert(mp(arr[bi], bi)); edg[bi].insert(mp(arr[ai], ai)); } set<pair<ll, ll> > all; // components and their sizes fori(n){ all.insert(mp(arr[i], i)); } while((ll)all.size() > 1){ auto it = all.begin(); ll hd = (*it).ss; all.erase(all.begin()); while(1){ auto it = edg[hd].begin(); edg[hd].erase(edg[hd].begin()); ll wh = (*it).ss; if(aid[wh] == hd){ continue; } else{ if(s[hd] >= arr[wh]){ ll hr = aid[wh]; all.erase(mp(s[hr], hr)); ll cr = join(hd, hr); all.insert(mp(s[cr], cr)); } else{ good[hd].clear(); } break; } } } ll cr = aid[0]; vector<bool> ans(n, 0); for(auto& el : good[cr]){ ans[el] = 1; } fori(n){ cout<<ans[i]; } } int main(){ cin.tie(0); ios_base::sync_with_stdio(0); deal(); }
#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...