oj.uz

Submission #642297

# Submission time Handle Problem Language Result Execution time Memory
642297 2022-09-19T08:04:32 Z dozer Joker (BOI20_joker) C++14
25 / 100
 83 ms 5748 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 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 Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.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 Incorrect 0 ms 340 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 61 ms 5392 KB Output is correct
4 Correct 60 ms 5136 KB Output is correct
5 Correct 74 ms 5624 KB Output is correct
6 Correct 83 ms 5232 KB Output is correct
7 Correct 61 ms 5140 KB Output is correct
8 Correct 66 ms 5028 KB Output is correct
9 Correct 67 ms 5240 KB Output is correct
10 Correct 65 ms 5580 KB Output is correct
11 Correct 71 ms 5216 KB Output is correct
12 Correct 64 ms 5748 KB Output is correct
13 Correct 62 ms 4720 KB Output is correct
14 Correct 65 ms 4848 KB Output is correct
15 Correct 67 ms 5212 KB Output is correct
16 Correct 76 ms 5420 KB Output is correct

Subtask #4
0 / 10.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 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.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 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.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 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -