oj.uz

Submission #948190

# Submission time Handle Problem Language Result Execution time Memory
948190 2024-03-17T20:20:19 Z amirhoseinfar1385 Stranded Far From Home (BOI22_island) C++17
0 / 100
 434 ms 54088 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
vector<int>adj[maxn];
int all[maxn],n,m,dp[maxn],vis[maxn],mishe[maxn],mn[maxn];

struct cmp {
    bool operator() (int a, int b) const {
		if(all[a]==all[b]){
			return a<b;
		}
		return all[a]<all[b];
    }
};

struct dsu{
	int par[maxn],sum[maxn],mx[maxn];
	set<int,cmp>st[maxn];
	dsu(){
		for(int i=0;i<maxn;i++){
			par[i]=i;
		}
	}
	int root(int u){
		if(u==par[u]){
			return u;
		}
		return par[u]=root(par[u]);
	}
	void con(int u,int v){
		int rootu=root(u),rootv=root(v);
		if(rootu!=rootv){
			if((int)st[rootu].size()<(int)st[rootv].size()){
				swap(rootu,rootv);
			}
			par[rootv]=rootu;
			sum[rootu]+=sum[rootv];
			mx[rootu]=max(mx[rootu],mx[rootv]);
			for(auto x:st[rootv]){
				st[rootu].insert(x);
			}
			while((int)st[rootu].size()>0&&mx[rootu]>=all[(*st[rootu].begin())]){
				st[rootu].erase(*st[rootu].begin());
			}
		}
	}
	long long porssum(int u){
		int v=root(u);
		return sum[v];
	}
	int porsy(int u){
		int v=root(u);
		if((int)st[v].size()==0){
			return -1;
		}
		return (*st[v].begin());
	}
}ds;

void vorod(){
	cin>>n>>m;
	all[0]=1e9+5;
	for(int i=1;i<=n;i++){
		cin>>all[i];
		ds.sum[i]=all[i];
		ds.mx[i]=all[i];
	}
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		//cout<<"ha "<<u<<" "<<v<<endl;
		ds.st[u].insert(v);
		ds.st[v].insert(u);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

void pre(){
	vector<pair<int,int>>so;
	for(int i=1;i<=n;i++){
		so.push_back(make_pair(all[i],i));
	}
	sort(so.begin(),so.end());
	vector<int>now;
	for(int i=0;i<n;i++){
		if(i>0&&so[i].first!=so[i-1].first){
			for(auto x:now){
				dp[x]=ds.porssum(x);
				mn[x]=ds.porsy(x);
			}
			now.clear();
		}
		int u=so[i].second;
		now.push_back(u);
		vis[u]=1;
		for(auto x:adj[u]){
			if(vis[x]==1){
				ds.con(x,u);
			}
		}
	}
	for(auto x:now){
		dp[x]=ds.porssum(x);
		mn[x]=ds.porsy(x);
	}
	now.clear();
}

void solve(){
	vector<pair<int,int>>so;
	for(int i=1;i<=n;i++){
		so.push_back(make_pair(all[i],i));
	}
	sort(so.begin(),so.end());
	for(int i=n-1;i>=0;i--){
		int u=so[i].second;
		//cout<<u<<" "<<dp[u]<<" "<<mn[u]<<endl;
		if(all[u]==so.back().first){
			mishe[u]=1;
		}
		if(mn[u]==-1||mishe[mn[u]]==0||dp[u]<all[mn[u]]){
			mishe[u]|=0;
		}else{
			mishe[u]|=1;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<mishe[i];
	}
	cout<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20568 KB Output is correct
2 Correct 5 ms 20572 KB Output is correct
3 Correct 4 ms 20588 KB Output is correct
4 Incorrect 6 ms 21084 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20568 KB Output is correct
2 Correct 5 ms 20572 KB Output is correct
3 Correct 4 ms 20588 KB Output is correct
4 Incorrect 6 ms 21084 KB Output isn't correct
5 Halted 0 ms 0 KB -