oj.uz

Submission #710948

# Submission time Handle Problem Language Result Execution time Memory
710948 2023-03-16T06:05:35 Z ld_minh4354 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 14604 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],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

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.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 Correct 157 ms 5128 KB Output is correct
5 Correct 144 ms 5116 KB Output is correct
6 Correct 216 ms 5132 KB Output is correct
7 Correct 162 ms 5152 KB Output is correct
8 Correct 111 ms 5120 KB Output is correct
9 Correct 260 ms 5284 KB Output is correct
10 Correct 67 ms 5128 KB Output is correct
11 Correct 66 ms 5124 KB Output is correct
12 Correct 60 ms 5076 KB Output is correct
13 Correct 109 ms 5116 KB Output is correct
14 Correct 90 ms 5132 KB Output is correct

Subtask #2
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 Execution timed out 1089 ms 14604 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1064 ms 12884 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1072 ms 14180 KB Time limit exceeded
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 Correct 157 ms 5128 KB Output is correct
5 Correct 144 ms 5116 KB Output is correct
6 Correct 216 ms 5132 KB Output is correct
7 Correct 162 ms 5152 KB Output is correct
8 Correct 111 ms 5120 KB Output is correct
9 Correct 260 ms 5284 KB Output is correct
10 Correct 67 ms 5128 KB Output is correct
11 Correct 66 ms 5124 KB Output is correct
12 Correct 60 ms 5076 KB Output is correct
13 Correct 109 ms 5116 KB Output is correct
14 Correct 90 ms 5132 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Execution timed out 1089 ms 14604 KB Time limit exceeded
18 Halted 0 ms 0 KB -