oj.uz

Submission #255983

# Submission time Handle Problem Language Result Execution time Memory
255983 2020-08-02T07:30:00 Z 임성재(#5031) Joker (BOI20_joker) C++17
25 / 100
 1561 ms 4820 KB 
#include<bits/stdc++.h>  
using namespace std;  
  
#define fast ios::sync_with_stdio(false);cin.tie(NULL)  
#define fi first  
#define se second  
#define all(v) (v).begin(),(v).end()  
#define pb push_back  
#define eb emplace_back
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair
  
typedef long long ll;  
typedef pair<int,int> pii;  
typedef pair<ll,ll> pll;  
const long long INF = 1e18;
const int inf = 1e9;

int n, m, q;
int l, r;
vector<pii> e;
int p[200010];
int rk[200010];
bool val[200010];
bool pval[200010];
int ans[200010];

int Find(int a) {
	if(p[a] == a) return a;

	int ret = Find(p[a]);
	val[a] = val[p[a]] ^ pval[a];
	
	return ret;
}

void Union(int i, int j) {
	int a = Find(i);
	int b = Find(j);

	if(rk[a] < rk[b]) p[a] = b, pval[a] = 1 ^ val[i] ^ val[j];
	else if(rk[b] < rk[a]) p[b] = a, pval[b] = 1 ^ val[i] ^ val[j];
	else p[b] = a, rk[a]++, pval[b] = 1 ^ val[i] ^ val[j];
}

int main() {
	fast;

	cin >> n >> m >> q;


	for(int i=1; i<=m; i++) {
		int u, v;

		cin >> u >> v;

		e.eb(u, v);
	}

	reverse(all(e));

	for(int l=1; l<=min(200, m); l++) {
		for(int i=1; i<=n; i++) p[i] = i, pval[i] = 0, val[i] = 0;

		for(int k = m - l + 1; k<m; k++) {
			auto i = e[k];
			if(Find(i.fi) == Find(i.se)) continue;

			Union(i.fi, i.se);
		}

		for(int k=0; k<m; k++) {
			auto i = e[k];
			if(Find(i.fi) == Find(i.se)) {
				if((val[i.fi] ^ val[i.se]) == 0) {
					ans[l] = m - k;
					break;
				}
				else continue;
			}

			Union(i.fi, i.se);
		}
	}

	while(q--) {
		cin >> l >> r;

		if(r < ans[l]) cout << "YES\n";
		else cout << "NO\n";
	}
	
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 678 ms 3664 KB Output is correct
4 Correct 1561 ms 4560 KB Output is correct
5 Correct 236 ms 4484 KB Output is correct
6 Correct 210 ms 3688 KB Output is correct
7 Correct 233 ms 3836 KB Output is correct
8 Correct 465 ms 3432 KB Output is correct
9 Correct 463 ms 3944 KB Output is correct
10 Correct 841 ms 4820 KB Output is correct
11 Correct 904 ms 3728 KB Output is correct
12 Correct 711 ms 4456 KB Output is correct
13 Correct 1046 ms 2924 KB Output is correct
14 Correct 470 ms 3304 KB Output is correct
15 Correct 732 ms 4076 KB Output is correct
16 Correct 826 ms 4668 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -