oj.uz

Submission #710991

# Submission time Handle Problem Language Result Execution time Memory
710991 2023-03-16T06:46:49 Z ld_minh4354 Stranded Far From Home (BOI22_island) C++17
40 / 100
 1000 ms 30996 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],cur_s;
vector<int> adj[200005],nodes;
bool vis[200005];

void dfs(int x,int max_s)
{
	if (vis[x]) return;
	vis[x]=true;
	
	cur_s += s[x];
	nodes.pb(x);
	
	for (auto y:adj[x]) dfs(y,max_s);
}

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,pos,next_sval;
	pair<int,int> p[200005],ed[200005];
	priority_queue<pair<int,int>> q;
	set<int> sval;
	
	cin>>n>>m;
	for (i=1;i<n+1;i++) cin>>s[i];
	for (i=1;i<m+1;i++) cin>>ed[i].fi>>ed[i].se;
	
	for (i=1;i<n+1;i++) sval.insert(s[i]);
	sval.insert(1e18);
	
	for (i=1;i<n+1;i++) ans[i]=1;
	for (auto x:sval) if (x!=1e18)
	{
		for (i=1;i<n+1;i++) while (adj[i].size()>0) adj[i].pop_back();
		
		for (i=1;i<m+1;i++) if (s[ed[i].fi]<=x and s[ed[i].se]<=x)
		{
			adj[ed[i].fi].pb(ed[i].se);
			adj[ed[i].se].pb(ed[i].fi);
		}
		
		for (i=1;i<n+1;i++) vis[i]=false;
		next_sval=*sval.upper_bound(x);
		
		for (i=1;i<n+1;i++) if (!vis[i] and s[i]<=x)
		{
			cur_s=0;
			while (nodes.size()>0) nodes.pop_back();
			
			dfs(i,x);
//			cout<<x<<" "<<i<<" "<<cur_s<<"\n";
			
			if (cur_s<next_sval and next_sval!=1e18) for (auto y:nodes) ans[y]=0;
		}
		
//		for (i=1;i<n+1;i++) cout<<ans[i];
//		cout<<"\n";
	}
	
	for (i=1;i<n+1;i++) cout<<ans[i];	
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:33:8: warning: unused variable 'j' [-Wunused-variable]
   33 |  int i,j,pos,next_sval;
      |        ^
island.cpp:33:10: warning: unused variable 'pos' [-Wunused-variable]
   33 |  int i,j,pos,next_sval;
      |          ^~~
island.cpp:34:16: warning: unused variable 'p' [-Wunused-variable]
   34 |  pair<int,int> p[200005],ed[200005];
      |                ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 4 ms 8036 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 71 ms 8380 KB Output is correct
5 Correct 62 ms 8464 KB Output is correct
6 Correct 5 ms 8280 KB Output is correct
7 Correct 49 ms 8344 KB Output is correct
8 Correct 45 ms 8340 KB Output is correct
9 Correct 7 ms 8296 KB Output is correct
10 Correct 65 ms 8460 KB Output is correct
11 Correct 73 ms 8492 KB Output is correct
12 Correct 42 ms 8372 KB Output is correct
13 Correct 6 ms 8300 KB Output is correct
14 Correct 12 ms 8276 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 5 ms 8160 KB Output is correct
3 Execution timed out 1067 ms 25432 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Execution timed out 1046 ms 25120 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8156 KB Output is correct
2 Correct 406 ms 26064 KB Output is correct
3 Correct 354 ms 23344 KB Output is correct
4 Correct 373 ms 23292 KB Output is correct
5 Correct 164 ms 23308 KB Output is correct
6 Correct 189 ms 24432 KB Output is correct
7 Correct 119 ms 24604 KB Output is correct
8 Correct 86 ms 28216 KB Output is correct
9 Correct 177 ms 19012 KB Output is correct
10 Correct 201 ms 23320 KB Output is correct
11 Correct 362 ms 30996 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8148 KB Output is correct
2 Correct 4 ms 8036 KB Output is correct
3 Correct 5 ms 8148 KB Output is correct
4 Correct 71 ms 8380 KB Output is correct
5 Correct 62 ms 8464 KB Output is correct
6 Correct 5 ms 8280 KB Output is correct
7 Correct 49 ms 8344 KB Output is correct
8 Correct 45 ms 8340 KB Output is correct
9 Correct 7 ms 8296 KB Output is correct
10 Correct 65 ms 8460 KB Output is correct
11 Correct 73 ms 8492 KB Output is correct
12 Correct 42 ms 8372 KB Output is correct
13 Correct 6 ms 8300 KB Output is correct
14 Correct 12 ms 8276 KB Output is correct
15 Correct 4 ms 8148 KB Output is correct
16 Correct 5 ms 8160 KB Output is correct
17 Execution timed out 1067 ms 25432 KB Time limit exceeded
18 Halted 0 ms 0 KB -