Submission #642316

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
642316	2022-09-19T08:30:03 Z	dozer	Joker (BOI20_joker)	C++14	25 / 100	106 ms	43264 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	19 ms	37844 KB	Output is correct
2	Correct	18 ms	37832 KB	Output is correct
3	Incorrect	20 ms	37852 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	37844 KB	Output is correct
2	Correct	18 ms	37832 KB	Output is correct
3	Incorrect	20 ms	37852 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	19 ms	37844 KB	Output is correct
2	Correct	18 ms	37832 KB	Output is correct
3	Correct	86 ms	43228 KB	Output is correct
4	Correct	106 ms	42956 KB	Output is correct
5	Correct	84 ms	43088 KB	Output is correct
6	Correct	76 ms	42764 KB	Output is correct
7	Correct	79 ms	42360 KB	Output is correct
8	Correct	84 ms	42356 KB	Output is correct
9	Correct	92 ms	42552 KB	Output is correct
10	Correct	79 ms	42920 KB	Output is correct
11	Correct	76 ms	42548 KB	Output is correct
12	Correct	83 ms	43264 KB	Output is correct
13	Correct	86 ms	42112 KB	Output is correct
14	Correct	86 ms	42196 KB	Output is correct
15	Correct	83 ms	42572 KB	Output is correct
16	Correct	82 ms	42828 KB	Output is correct