Submission #603987

#TimeUsernameProblemLanguageResultExecution timeMemory
603987Ahmadsm2005Stranded Far From Home (BOI22_island)C++17
10 / 100
1095 ms16264 KiB
#include <bits/stdc++.h> //#define int long long using namespace std; int N,M,V[200001],X,Y,VIS[200001]; int R[200001],R2[200001]; vector<int>edges[200001]; void BFS(int X){ for(int i = 0; i < N; i += 1)VIS[i] = 0; priority_queue<pair<int,int>>Q; int CNT = V[X]; Q.push({0,X}); vector<int>UU; while(Q.size()){ int F = Q.top().second,S = -Q.top().first; Q.pop(); if(VIS[F])continue; if((S > CNT) || (R[F] == 0 && R2[F] >= CNT)){ R[X] = 0; R2[X] = CNT; return; } if(R[F] == 1)break; VIS[F] = 1; CNT += S; CNT = min(CNT,(int)1e9); for(int i = 0; i < edges[F].size(); i += 1){ Q.push({-V[edges[F][i]],edges[F][i]}); } } R[X] = 1; } int32_t main() { cin.tie(0),iostream::sync_with_stdio(0); cin>>N>>M; vector<int>RR; mt19937 rng(2005); for(int i = 0; i < N; i += 1)RR.push_back(i); shuffle(RR.begin(),RR.end(),rng); for(int i = 0; i < N; i += 1){ cin>>V[i]; R[i] = -1; } for(int i = 0; i < M; i += 1){ cin>>X>>Y; edges[X - 1].push_back(Y - 1),edges[Y - 1].push_back(X - 1); } for(int i = 0; i < N; i += 1){ BFS(RR[i]); } for(int i = 0; i < N; i += 1)cout<<R[i]; }

Compilation message (stderr)

island.cpp: In function 'void BFS(int)':
island.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int i = 0; i < edges[F].size(); i += 1){
      |                        ~~^~~~~~~~~~~~~~~~~
#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...