Submission #839676

#	Time	Username	Problem	Language	Result	Execution time	Memory
839676		parsadox2	Stranded Far From Home (BOI22_island)	C++14	100 / 100	161 ms	28064 KiB

island

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 10;
int n , s[N] , m , pos[N] , dis[N] , par[N];
vector <int> adj[N];

bool cmp(int a , int b)
{
	return s[a] < s[b];
}

int root(int v)
{
	if(par[v] < 0)
		return v;
	int R = root(par[v]);
	dis[v] |= dis[par[v]];
	par[v] = R;
	return R;
}

void Add(int v)
{
	vector <int> vec;
	for(auto u : adj[v])  if(pos[u] < pos[v])
		vec.push_back(root(u));
	int tmp = 0;
	for(auto u : vec)
	{
		if(par[u] >= 0)
			continue;
		//cout << v << " : " << u << " " << par[u] << endl;
		if(abs(par[u]) < s[v])
		{
			dis[u] = 1;
			//cout << v << " : " << u << endl;
		}
		par[v] += par[u];
		par[u] = v;
	}
	//cout << v << " = " << par[v] << endl;
}

void solve()
{
	cin >> n >> m;
	vector <int> vec;
	int sum = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		cin >> s[i];
		sum -= s[i];
		vec.push_back(i);
	}
	for(int i = 0 ; i < m ; i++)
	{
		int v , u;  cin >> v >> u;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	sort(vec.begin() , vec.end() , cmp);
	for(int i = 0 ; i < n ; i++)
		pos[vec[i]] = i;
	for(int i = 1 ; i <= n ; i++)
	{
		par[i] = -s[i];
		dis[i] = 0;
	}
	for(auto u : vec)
		Add(u);
	for(int i = 1 ; i <= n ; i++)
	{
		int tmp = root(i);
		cout << ((dis[i] == 0 && par[tmp] == sum) ? 1 : 0);
	}
	cout << endl;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);
	int Tc;
	Tc = 1;
	while(Tc--)
		solve();
	return 0;
}

Compilation message (stderr)

island.cpp: In function 'void Add(long long int)':
island.cpp:29:6: warning: unused variable 'tmp' [-Wunused-variable]
   29 |  int tmp = 0;
      |      ^~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35