Submission #642280

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
642280	2022-09-19T07:21:34 Z	dozer	Joker (BOI20_joker)	C++14	25 / 100	79 ms	9496 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 200005

const int modulo = 1e9 + 7;
int root[N], ans[N], u[N], v[N], l[N], r[N];

int find(int node)
{
	if (node < 0) return -(find(-node));
	if (node == root[node]) return node;
	return root[node] = find(root[node]);
}


int32_t main()
{
	
	fastio();


	int n, m, q;
	cin>>n>>m>>q;
	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 = m; i >= 1; i--)
	{
		if (ans[i + 1] == 1) 
		{
			ans[i] = 1;
			continue;
		}
		int a = find(u[i]), b = find(v[i]);
		if (a == b) ans[i] = 1;
		else if (a < 0) a *= -1, b *= -1;
		root[a] = -b;
	}

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

Subtask #1
0 / 6.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Incorrect	340 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Incorrect	340 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	64 ms	5312 KB	Output is correct
4	Correct	79 ms	5108 KB	Output is correct
5	Correct	74 ms	5448 KB	Output is correct
6	Correct	61 ms	9024 KB	Output is correct
7	Correct	61 ms	8864 KB	Output is correct
8	Correct	76 ms	8072 KB	Output is correct
9	Correct	67 ms	8264 KB	Output is correct
10	Correct	64 ms	8996 KB	Output is correct
11	Correct	63 ms	8852 KB	Output is correct
12	Correct	65 ms	9496 KB	Output is correct
13	Correct	75 ms	8384 KB	Output is correct
14	Correct	70 ms	8624 KB	Output is correct
15	Correct	67 ms	8940 KB	Output is correct
16	Correct	66 ms	9280 KB	Output is correct