oj.uz

답안 #581873

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
581873 2022-06-23T07:34:56 Z temporary_juggernaut Stranded Far From Home (BOI22_island) C++17
0 / 100
 4 ms 4948 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
ll a[200005];
int par[200005];
ll sum[200005];
vector<int>comp[200005];
ll mx[200005];
int n,m;
int cash;
bool cmp(pair<int,int>l,pair<int,int>r){
	if(a[l.fr]==a[r.fr])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;
	for(int to:comp[b])comp[a].push_back(to);
	comp[b].clear();
}
int ans[200005];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		mx[i]=a[i];
		sum[i]=a[i];
		comp[i].push_back(i);
		par[i]=i;
	}
	vector<pair<pair<ll,ll>,pair<int,int>>>edges;
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		if(a[x]<a[y])swap(x,y);
		edges.push_back(make_pair(make_pair(a[x],a[y]),make_pair(x,y)));
	}
	sort(edges.begin(),edges.end());
	for(int i=1;i<=m;i++)unite(edges[i-1].sc.fr,edges[i-1].sc.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:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
island.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%lld",&a[i]);
      |   ~~~~~^~~~~~~~~~~~~~
island.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 4 ms 4948 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 4 ms 4948 KB Output isn't correct
4 Halted 0 ms 0 KB -