oj.uz

Submission #642456

# Submission time Handle Problem Language Result Execution time Memory
642456 2022-09-19T13:32:33 Z dozer Joker (BOI20_joker) C++14
25 / 100
 176 ms 18108 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].begin(), block[i].end());
		stack<pii> sl;
		int last = m;
		for (auto j : block[i])
		{
			while(!sl.empty())
			{
				root[sl.top().st] = sl.top().nd;
				sl.pop();
			}
			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 6 ms 9640 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Incorrect 7 ms 9684 KB Output isn't correct
6 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 6 ms 9640 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Incorrect 7 ms 9684 KB Output isn't correct
6 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 6 ms 9640 KB Output is correct
3 Correct 110 ms 17108 KB Output is correct
4 Correct 150 ms 17332 KB Output is correct
5 Correct 159 ms 17732 KB Output is correct
6 Correct 116 ms 17248 KB Output is correct
7 Correct 113 ms 17084 KB Output is correct
8 Correct 116 ms 16892 KB Output is correct
9 Correct 130 ms 17284 KB Output is correct
10 Correct 146 ms 17996 KB Output is correct
11 Correct 122 ms 17168 KB Output is correct
12 Correct 176 ms 18108 KB Output is correct
13 Correct 94 ms 16444 KB Output is correct
14 Correct 113 ms 16840 KB Output is correct
15 Correct 139 ms 17460 KB Output is correct
16 Correct 157 ms 18052 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 6 ms 9640 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Incorrect 7 ms 9684 KB Output isn't correct
6 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 6 ms 9640 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Incorrect 7 ms 9684 KB Output isn't correct
6 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 6 ms 9640 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Incorrect 7 ms 9684 KB Output isn't correct
6 Halted 0 ms 0 KB -