oj.uz

Submission #255981

# Submission time Handle Problem Language Result Execution time Memory
255981 2020-08-02T07:27:41 Z 임성재(#5031) Joker (BOI20_joker) C++17
25 / 100
 1609 ms 4768 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, n); l++) {
		for(int i=1; i<=n; i++) p[i] = i, pval[i] = 0, val[i] = 0;

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

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

		for(int k=0; k<e.size(); 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";
	}
	
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:65:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=e.size() - l + 1; k<e.size(); k++) {
                               ~^~~~~~~~~
Joker.cpp:72:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0; k<e.size(); k++) {
                ~^~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 706 ms 3628 KB Output is correct
4 Correct 1609 ms 4584 KB Output is correct
5 Correct 242 ms 4580 KB Output is correct
6 Correct 219 ms 3688 KB Output is correct
7 Correct 232 ms 3688 KB Output is correct
8 Correct 458 ms 3556 KB Output is correct
9 Correct 443 ms 3816 KB Output is correct
10 Correct 819 ms 4768 KB Output is correct
11 Correct 869 ms 3816 KB Output is correct
12 Correct 690 ms 4516 KB Output is correct
13 Correct 1038 ms 2956 KB Output is correct
14 Correct 465 ms 3336 KB Output is correct
15 Correct 748 ms 4124 KB Output is correct
16 Correct 824 ms 4688 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -