Submission #714649

#TimeUsernameProblemLanguageResultExecution timeMemory
714649Ferid20072020Stranded Far From Home (BOI22_island)C++14
0 / 100
191 ms31108 KiB
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define ld long double #define ui unsigned int #define f first #define s second #define ins insert #define pb push_back #define mp make_pair #define ln '\n' #define int ll #define pii pair<int , int> #define INF LLONG_MAX #define vv(a) vector<a> #define pp(a, b) pair<a, b> #define pq(a) priority_queue<a> #define qq(a) queue<a> #define ss(a) set<a> #define mss(a) multiset<a> #define mm(a, b) map<a, b> #define mmm(a , b) multimap<a , b> #define sz(x) (x).size() #define all(x) (x).begin() , (x).end() #define fastio \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// const int MAX = 200005; int n , m; vv(vv(int)) g(MAX); vv(int) tot(MAX) , tot1(MAX) , tot2(MAX); vv(int) tt(MAX); vv(int) color(MAX , 0); vv(int) parent(MAX); int lvl = 1; void DFS(int src){ color[src] = 1; tt[src] = lvl; for(auto to : g[src]){ if(color[to] == 0){ parent[to] = src; DFS(to); } } } void solve(){ cin >> n >> m; for(int i=1 ; i<=n ; i++){ cin >> tot[i]; } tot2 = tot; for(int i=0 ; i<m ; i++){ int u , v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } if(n == 1){ cout << 1; return; } DFS(1); vv(pii) Sr; for(int i=1 ; i<=n ; i++){ Sr.pb({tt[i] , i}); } sort(all(Sr)); reverse(all(Sr)); tot1 = tot; for(int i=0 ; i<Sr.size() ; i++){ if(tot1[Sr[i].s] < tot1[parent[Sr[i].s]]){ tot1[parent[Sr[i].s]] += tot1[Sr[i].s]; } else if(tot1[Sr[i].s] > tot1[parent[Sr[i].s]]){ tot1[Sr[i].s] += tot1[parent[Sr[i].s]]; } else{ tot1[parent[Sr[i].s]] += tot1[Sr[i].s]; tot1[Sr[i].s] += tot1[parent[Sr[i].s]]; } } sort(all(tot2)); reverse(all(tot2)); for(int i=1 ; i<=n ; i++){ int Max = tot2[0]; if(tot[i] == Max){ Max = tot2[1]; } if(tot1[i] >= Max){ cout << 1; } else{ cout << 0; } } } signed main(){ fastio int t = 1; //cin >> t; while(t--){ solve(); } return 0; }

Compilation message (stderr)

island.cpp: In function 'void solve()':
island.cpp:83:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i=0 ; i<Sr.size() ; 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...