oj.uz

Submission #967598

# Submission time Handle Problem Language Result Execution time Memory
967598 2024-04-22T13:29:15 Z dong_gas Stranded Far From Home (BOI22_island) C++17
0 / 100
 519 ms 61820 KB 
#include <bits/extc++.h>
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ll n, m, a[200020];

struct disjoin_set{
	ll papa[200020], height[200020], sum[200020];
	void init() {
		memset(papa,-1,sizeof(papa));
		memset(height,0,sizeof(height));
		for(ll i=1;i<=n;i++) sum[i]=a[i];
	}
	ll Find(ll u) {
		if(papa[u]==-1) return u;
		return papa[u]=Find(papa[u]);
	}
	bool Union(ll u,ll v) {
		u=Find(u), v=Find(v);
		if(u==v) return false;
		if(height[u]<height[v]) swap(u,v);
		papa[v]=u;
		if(height[u]==height[v]) height[u]++;
		sum[u]+=sum[v];
		return true;
	}
} djs;

vector<ll> adj[200020], x;
bool chk[200020], visited[200020];
unordered_map<ll, ll> ma;
map<ll, vector<pll>> edges;

void dfs(ll u, ll p) {
	visited[u]=1;
	for(ll& v:adj[u]) if(!chk[v] && v!=p) dfs(v, u);
}

void solve() {
    cin>>n>>m;
	for(ll i=1;i<=n;i++) cin>>a[i], x.emplace_back(a[i]);
	zip(x);
	for(ll i=0;i<x.size();i++) {
		if(i+1<(ll)x.size()) ma[x[i]]=x[i+1];
		else ma[x[i]]=0;
	}
	while(m --> 0) {
		ll u, v; cin>>u>>v;
		if(u>v) swap(u,v);
		if(a[u]<a[v]) swap(u,v);
		edges[a[u]].emplace_back(u,v);
		edges[a[v]].emplace_back(v,v);
	}
	djs.init();

	for(auto [p, vec]: edges) {
		//cout<<p<<'\n';
		//for(auto [u,v]:vec) cout<<u<<' '<<v<<endl;
		//cout<<endl;
		ll nxt_val=ma[p];
		for(auto [u, v]: vec) if(djs.Union(u,v)) adj[u].emplace_back(v), adj[v].emplace_back(u);
		for(auto [u, v]: vec) if(djs.sum[djs.Find(u)]<nxt_val) {
			chk[u]=1;
			//cout<<"Here:";
			//cout<<u<<' '<<v<<' '<<p<<endl;
		}
	}
	//for(ll i=1;i<=n;i++) cout<<chk[i]<<' ';
	//cout<<endl;
	for(ll i=1;i<=n;i++) if(a[i]==x.back() && !visited[i]) dfs(i,0);
	for(ll i=1;i<=n;i++) cout<<visited[i];
	
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc=1; //cin>>tc;
    while(tc--) solve();
}

Compilation message

island.cpp: In function 'void solve()':
island.cpp:49:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(ll i=0;i<x.size();i++) {
      |             ~^~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 372 ms 61820 KB Output is correct
4 Correct 93 ms 35312 KB Output is correct
5 Incorrect 421 ms 58212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

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