oj.uz

Submission #839636

# Submission time Handle Problem Language Result Execution time Memory
839636 2023-08-30T11:03:55 Z parsadox2 Stranded Far From Home (BOI22_island) C++14
0 / 100
 145 ms 20256 KB 
#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));
	for(auto u : vec)
	{
		if(par[u] >= 0)
			continue;
		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

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.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 5072 KB Output is correct
3 Incorrect 145 ms 20256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 137 ms 19140 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 4948 KB Output is correct
2 Incorrect 142 ms 20228 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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