Submission #710948

#	Time	Username	Problem	Language	Result	Execution time	Memory
710948		ld_minh4354	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1089 ms	14604 KiB

island

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define debug(x) cout<<#x<<": "<<x<<"\n"

int n,m,s[200005],ans[200005],sums[200005],pref[200005];
vector<int> adj[200005];
bool vis[200005];

signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("input.000","r",stdin);
//	freopen("output.000","w",stdout);
//	srand((unsigned)time(NULL));
//	rand()
	
	int i,j,x,pos,u,v,cur_s;
	pair<int,int> p[200005];
	priority_queue<pair<int,int>> q;
	set<int> sl,sr;
	
	cin>>n>>m;
	for (i=1;i<n+1;i++) cin>>s[i];
	for (i=1;i<m+1;i++)
	{
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	
	for (x=1;x<n+1;x++)
	{
		for (i=1;i<n+1;i++) vis[i]=false;
		
		vis[x]=true;q.push({0,x});cur_s=0;ans[x]=1;
		
//		cout<<x<<": ";
		
		while (!q.empty())
		{
			u=q.top().se;q.pop();
//			cout<<u<<" ";
			
			if (cur_s<s[u] and u!=x)
			{
				ans[x]=0;
				while (!q.empty()) q.pop();
			}
			else
			{
				cur_s+=s[u];
				for (auto y:adj[u])
				{
					if (vis[y]) continue;
					vis[y]=true;
					q.push({-s[y],y});
				}
			}
		}
//		cout<<"\n";
	}
	
	for (i=1;i<n+1;i++) cout<<ans[i];
		
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:22:8: warning: unused variable 'j' [-Wunused-variable]
   22 |  int i,j,x,pos,u,v,cur_s;
      |        ^
island.cpp:22:12: warning: unused variable 'pos' [-Wunused-variable]
   22 |  int i,j,x,pos,u,v,cur_s;
      |            ^~~
island.cpp:23:16: warning: unused variable 'p' [-Wunused-variable]
   23 |  pair<int,int> p[200005];
      |                ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35