Submission #642317

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
642317	2022-09-19T08:30:47 Z	dozer	Joker (BOI20_joker)	C++14	25 / 100	94 ms	46328 KB

Joker

#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;
vector<int> ind[N], root, gh[N];
map<int, int> res[N];

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


int32_t main()
{
	fastio();


	int m, q;
	cin>>n>>m>>q;
	root.resize(n + 5, 0);
	for (int i = 1; i <= n; i++)
		root[i] = i;

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

	for (int i = 1; i <= q; i++)
	{
		cin>>l[i]>>r[i];
		ind[r[i]].pb(l[i]);
	}

	for (int i = m; i >= 1; i--)
	{
		/*
		if (ind[i].size() > 0)
		{
			for (auto j : root) gh[i].pb(j);
		}
		*/
		if (ans[i] == 1) 
		{
			ans[i - 1] = 1;
			continue;
		}
		int a = find(root, u[i]), b = find(root, v[i]);
		if (a == b) 
		{
			ans[i - 1] = 1;
		}
		else
		{
			if (a < 0) a *= -1, b *= -1;
			root[a] = -b;
		}
		//cout<<i<<sp<<ans[i]<<endl;
	}
/*
	for (int i = m; i >= 1; i--)
	{
		sort(ind[i].begin(), ind[i].end());
		if (gh[i].empty() || ans[i] == 1) continue;
		int last = 1;
		for (auto j : ind[i])
		{
			if (res[i][last] == 1) 
			{
				res[i][j] = 1;
				last = j;
				continue;
			}
			for (int k = last; k < j; k++)
			{
				int a = find(gh[i], u[k]), b = find(gh[i], v[k]);
				if (a == b)
				{
					res[i][j] = 1;
					break;
				} 
				if (a < 0) a *= -1, b *= -1;
				gh[i][a] = -b;
			}
			last = j;
		}
	}
*/
	for (int i = 1; i <= q; i++)
	{
		//if (res[r[i]][l[i]] || ans[r[i]]) cout<<"YES\n";
		if (ans[r[i]]) cout<<"YES\n";
		else cout<<"NO\n";
	}
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	37900 KB	Output is correct
2	Correct	20 ms	37844 KB	Output is correct
3	Incorrect	19 ms	37856 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	37900 KB	Output is correct
2	Correct	20 ms	37844 KB	Output is correct
3	Incorrect	19 ms	37856 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	37900 KB	Output is correct
2	Correct	20 ms	37844 KB	Output is correct
3	Correct	86 ms	46328 KB	Output is correct
4	Correct	86 ms	45132 KB	Output is correct
5	Correct	87 ms	45300 KB	Output is correct
6	Correct	85 ms	44976 KB	Output is correct
7	Correct	87 ms	44696 KB	Output is correct
8	Correct	88 ms	44692 KB	Output is correct
9	Correct	89 ms	44844 KB	Output is correct
10	Correct	94 ms	45124 KB	Output is correct
11	Correct	93 ms	44808 KB	Output is correct
12	Correct	89 ms	45484 KB	Output is correct
13	Correct	90 ms	44272 KB	Output is correct
14	Correct	92 ms	44544 KB	Output is correct
15	Correct	90 ms	44776 KB	Output is correct
16	Correct	93 ms	45004 KB	Output is correct