oj.uz

Submission #710927

# Submission time Handle Problem Language Result Execution time Memory
710927 2023-03-16T05:29:53 Z ld_minh4354 Stranded Far From Home (BOI22_island) C++17
10 / 100
 205 ms 28876 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 145 ms 22272 KB Output is correct
4 Correct 115 ms 22348 KB Output is correct
5 Correct 165 ms 16984 KB Output is correct
6 Correct 170 ms 17420 KB Output is correct
7 Correct 160 ms 17504 KB Output is correct
8 Correct 189 ms 17448 KB Output is correct
9 Correct 137 ms 18680 KB Output is correct
10 Correct 84 ms 17880 KB Output is correct
11 Correct 93 ms 17844 KB Output is correct
12 Correct 128 ms 17360 KB Output is correct
13 Correct 126 ms 28816 KB Output is correct
14 Correct 139 ms 28812 KB Output is correct
15 Correct 138 ms 28876 KB Output is correct
16 Correct 82 ms 28568 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 148 ms 28736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4948 KB Output is correct
2 Incorrect 205 ms 18160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 3 ms 5076 KB Output isn't correct
5 Halted 0 ms 0 KB -