Submission #839635

#	Time	Username	Problem	Language	Result	Execution time	Memory
839635		parsadox2	Stranded Far From Home (BOI22_island)	C++17	0 / 100	119 ms	35052 KiB

island

#include <bits/stdc++.h>

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));
	sort(vec.begin() , vec.end());
	vec.resize(unique(vec.begin() , vec.end()) - vec.begin());
	for(auto u : vec)
	{
		if(par[u] > par[v])
			dis[u] = 1;
		par[v] += par[u];
		par[u] = v;
	}
}

void solve()
{
	cin >> n >> m;
	vector <int> vec;
	for(int i = 1 ; i <= n ; i++)
	{
		cin >> 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];
	for(auto u : vec)
		Add(u);
	for(int i = 1 ; i <= n ; i++)
	{
		int tmp = root(i);
		cout << (dis[i] ^ 1);
	}
	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 solve()':
island.cpp:64:7: warning: unused variable 'tmp' [-Wunused-variable]
   64 |   int tmp = root(i);
      |       ^~~

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