oj.uz

Submission #642458

# Submission time Handle Problem Language Result Execution time Memory
642458 2022-09-19T13:41:09 Z dozer Joker (BOI20_joker) C++14
25 / 100
 158 ms 18156 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 400005

const int modulo = 1e9 + 7;
int ans[N], u[N], v[N], l[N], r[N], n, sz[N];
vector<int> root;
vector<pii> block[N];
int res[N], s;

int find(vector<int> &b, int node)
{
	if (node < 0) return -(find(b, -node));
	if (node == b[node]) return node;
	return b[node] = find(b, b[node]);
}


int32_t main()
{
	fastio();


	int m, q;
	cin>>n>>m>>q;
	root.resize(n + 5, 0);

	while(s * s < m) s++;
	for (int i = 1; i <= m; i++)
	{
		cin>>u[i]>>v[i];
	}

	int maks = 0;
	for (int i = 1; i <= q; i++)
	{
		cin>>l[i]>>r[i];
		block[l[i] / s].pb({r[i], i});
	}

	int it = 0;
	for (int i = 0; i <= m / s + 1; i++)
	{
		for (int j = 1; j <= n; j++) root[j] = j, sz[j] = 1;
		sort(block[i].rbegin(), block[i].rend());
		stack<pii> sl;
		int last = m;
		for (auto j : block[i])
		{
			while(!sl.empty())
			{
				root[sl.top().st] = sl.top().nd;
				sl.pop();
			}
			//cout<<j.nd<<sp<<l[j.nd]<<sp<<r[j.nd]<<endl;
			for (int k = 1; k < l[j.nd]; k++)
			{
				int a = find(root, u[k]), b = find(root, v[k]);
				if (a == b) 
				{
					res[j.nd] = 1;
					break;
				}
				else
				{
					if (sz[abs(a)] > sz[abs(b)]) swap(a, b);
					if (a < 0) a *= -1, b *= -1;
					sl.push({a, root[a]});
					root[a] = -b;
				}
			}
			while(last > r[j.nd])
			{
				int a = find(root, u[last]), b = find(root, v[last]);
				if (a == b) 
				{
					res[j.nd] = 1;
					break;
				}
				else
				{
					if (sz[abs(a)] > sz[abs(b)]) swap(a, b);
					if (a < 0) a *= -1, b *= -1;
					root[a] = -b;
				}
				last--;
			}
		}
	}
	

	for (int i = 1; i <= q; i++)
	{
		if (res[i]) cout<<"YES\n";
		else cout<<"NO\n";
	}
		
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Compilation message

Joker.cpp: In function 'int32_t main()':
Joker.cpp:42:6: warning: unused variable 'maks' [-Wunused-variable]
   42 |  int maks = 0;
      |      ^~~~
Joker.cpp:49:6: warning: unused variable 'it' [-Wunused-variable]
   49 |  int it = 0;
      |      ^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 5 ms 9668 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Incorrect 5 ms 9732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 5 ms 9668 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Incorrect 5 ms 9732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 116 ms 17652 KB Output is correct
4 Correct 158 ms 17444 KB Output is correct
5 Correct 152 ms 17744 KB Output is correct
6 Correct 118 ms 17340 KB Output is correct
7 Correct 125 ms 17336 KB Output is correct
8 Correct 114 ms 17092 KB Output is correct
9 Correct 119 ms 17344 KB Output is correct
10 Correct 151 ms 18156 KB Output is correct
11 Correct 127 ms 17416 KB Output is correct
12 Correct 153 ms 18116 KB Output is correct
13 Correct 95 ms 16660 KB Output is correct
14 Correct 111 ms 16992 KB Output is correct
15 Correct 151 ms 17568 KB Output is correct
16 Correct 152 ms 18044 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 5 ms 9668 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Incorrect 5 ms 9732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 5 ms 9668 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Incorrect 5 ms 9732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 5 ms 9668 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Incorrect 5 ms 9732 KB Output isn't correct
9 Halted 0 ms 0 KB -