Submission #255968

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
255968	2020-08-02T07:17:53 Z	임성재(#5031)	Joker (BOI20_joker)	C++17	25 / 100	114 ms	9448 KB

Joker

#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;
vector<int> g[200010];
int d[200010];
int p[200010];
int rk[200010];
bool val[200010];
bool pval[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 i=1; i<=n; i++) p[i] = i;

	int ans = 0;
	
	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 = m - k;
				break;
			}
			else continue;
		}

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

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

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

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:67:16: 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	4 ms	4992 KB	Output is correct
2	Correct	3 ms	4992 KB	Output is correct
3	Incorrect	3 ms	4992 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4992 KB	Output is correct
2	Correct	3 ms	4992 KB	Output is correct
3	Incorrect	3 ms	4992 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	4 ms	4992 KB	Output is correct
2	Correct	3 ms	4992 KB	Output is correct
3	Correct	91 ms	8012 KB	Output is correct
4	Correct	93 ms	9320 KB	Output is correct
5	Correct	88 ms	9192 KB	Output is correct
6	Correct	89 ms	8424 KB	Output is correct
7	Correct	92 ms	8424 KB	Output is correct
8	Correct	88 ms	8168 KB	Output is correct
9	Correct	85 ms	8556 KB	Output is correct
10	Correct	83 ms	9448 KB	Output is correct
11	Correct	101 ms	8384 KB	Output is correct
12	Correct	114 ms	9192 KB	Output is correct
13	Correct	100 ms	7532 KB	Output is correct
14	Correct	102 ms	8040 KB	Output is correct
15	Correct	95 ms	8808 KB	Output is correct
16	Correct	97 ms	9320 KB	Output is correct