Submission #710927

#	Time	Username	Problem	Language	Result	Execution time	Memory
710927		ld_minh4354	Stranded Far From Home (BOI22_island)	C++17	10 / 100	205 ms	28876 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];
vector<int> adj[200005];
bool vis[200005];

void dfs(int x)
{
	sums[x]=s[x];
	vis[x]=true;
	
	for (auto y:adj[x]) if (!vis[y])
	{
		dfs(y);
		sums[x] += sums[y];
	}
}

void dfsans(int x)
{
	vis[x]=true;
	ans[x]=1;
	for (auto y:adj[x]) if (!vis[y] and sums[y]>=s[x]) dfsans(y);
}

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,u,v,cur_s;
	bool tr;
	queue<int> q;
	
	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 (i=1;i<n+1;i++) vis[i]=false;
	dfs(1);
	
	for (i=1;i<n+1;i++)
	{
		vis[i]=false;
		ans[i]=0;
	}
	dfsans(1);
	
	for (i=1;i<n+1;i++) cout<<ans[i];
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:41:8: warning: unused variable 'j' [-Wunused-variable]
   41 |  int i,j,u,v,cur_s;
      |        ^
island.cpp:41:14: warning: unused variable 'cur_s' [-Wunused-variable]
   41 |  int i,j,u,v,cur_s;
      |              ^~~~~
island.cpp:42:7: warning: unused variable 'tr' [-Wunused-variable]
   42 |  bool tr;
      |       ^~

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