oj.uz

Submission #581854

# Submission time Handle Problem Language Result Execution time Memory
581854 2022-06-23T07:23:10 Z temporary_juggernaut Stranded Far From Home (BOI22_island) C++14
0 / 100
 4 ms 4964 KB 
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
int a[200005];
int par[200005];
ll sum[200005];
vector<int>comp[200005];
int mx[200005];
pair<int,int>edge[200005];
int n,m;
int cash;
bool cmp(pair<int,int>l,pair<int,int>r){
	if(a[l.fr]==a[r.fr]){
		if(a[l.sc]==a[r.sc])return l<r;
		return a[l.sc]<a[r.sc];
	}
	return a[l.fr]<a[r.fr];
}
int fin(int v){return v==par[v]?v:par[v]=fin(par[v]);}
void unite(int a,int b){
	a=fin(a);
	b=fin(b);
	if(a==b)return;
	if(comp[a].size()<comp[b].size())swap(a,b);
	if(sum[a]<mx[b])comp[a].clear();
	if(sum[b]<mx[a])comp[b].clear();
	par[b]=a;
	umax(mx[a],mx[b]);
	sum[a]+=sum[b];
	cash=a;
	comp[a].insert(comp[a].end(),comp[b].begin(),comp[b].end());
	comp[b].clear();
}
int ans[200005];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		mx[i]=a[i];
		sum[i]=a[i];
		comp[i].push_back(i);
		par[i]=i;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&edge[i].fr,&edge[i].sc);
		if(a[edge[i].fr]<a[edge[i].sc])swap(edge[i].fr,edge[i].sc);
	}
	sort(edge+1,edge+1+m,cmp);
	for(int i=1;i<=m;i++)unite(edge[i].fr,edge[i].sc);
	for(int to:comp[cash])ans[to]=1;
	for(int i=1;i<=n;i++)printf("%d",ans[i]);
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
island.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
island.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%d%d",&edge[i].fr,&edge[i].sc);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4960 KB Output isn't correct
2 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 4 ms 4964 KB Output is correct
3 Incorrect 2 ms 4948 KB Output isn't correct
4 Halted 0 ms 0 KB -