Submission #1033978

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1033978	2024-07-25T08:17:09 Z	goodspeed0208	Joker (BOI20_joker)	C++14	25 / 100	161 ms	12848 KB

Joker

#include<bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

int n, m, q;
vector<int>f, sz, same, dif;

void init() {
	for (int i = 0 ; i < n ; i++) {
		f[i] = i;
		same[i] = i;
		dif[i] = -1;
		sz[i] = 1;
	}
}

int find(int x) {
	//if (f[x][j] == -1) return -1;
	if (x == f[x]) return x;
	else return f[x] = find(f[x]);
}

int finds(int x) {
	if (x == -1) return -1;
	if (x == same[x]) return x;
	else return same[x] = finds(same[x]);
}

bool add(int a, int b) {
	int fa = find(a), fb = find(b);
	int sa = finds(a), sb = finds(b);
	//cout << fa << " " << sa << " " << fb << " " << sb << "\n";
	if (fa == fb) {
		if (sa == sb) return true;
		else return false;
	}
	/*if (sz[fa] > sz[fb]) {
		swap(fa, fb); swap(sa, sb);
	}*/
	f[fa] = fb;
	sz[fb] += sz[fa];
	//cout << fa << " " << dif[fa] << " " << finds(dif[fa]) << "\n";
	assert(dif[fa] == finds(dif[fa]));
	assert(dif[fb] == finds(dif[fb]));
	dif[fa] = finds(dif[fa]); dif[fb] = finds(dif[fb]);
	if ((fa == sa && fb == sb) || (fa != sa && fb != sb)) {
		if (dif[fa] != -1) same[dif[fa]] = fb;
		if (dif[fb] != -1) same[fa] = dif[fb];
		else dif[fb] = fa;
	} else {
		same[fa] = fb;
		if (dif[fa] != -1 && dif[fb] != -1) same[dif[fa]] = dif[fb];
		else if (dif[fa] != -1) dif[fb] = dif[fa];
	}
	//for (int i = 0 ; i < n ; i++) cout << find(i) << " "; cout << "\n";
	//for (int i = 0 ; i < n ; i++) cout << finds(i) << " "; cout <<"\n";
	//cout << "\n";
	return false;
}

signed main() {
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	cin >> n >> m >> q;
	f.resize(n);
	sz.resize(n);
	same.resize(n);
	dif.resize(n);
	vector<pii>e;
	int a, b;
	for (int i = 0 ; i < m ; i++) {
		cin >> a >> b; a--, b--;
		e.push_back({a, b});
	}
	int l, r;
	vector<pair<pii, int> >rg(q);
	for (int i = 0 ; i < q ; i++) {
		cin >> rg[i].first.first >> rg[i].first.second;
		rg[i].first.first--; rg[i].first.second--;
		rg[i].second = i;
	}
	sort(rg.begin(), rg.end(), [&](pair<pii, int> x, pair<pii, int> y) {return x.first.second < y.first.second;});
	vector<int>ans(q, 0);
	r = m-1;
	bool can = 0;
	init();
	for (int i = q-1 ; i >= 0 ; i--) {
		//cout <<can << " " << rg[i].first.second << "\n";
		if (can) {
			ans[rg[i].second] = 1;
			continue;
		}
		while (!can && r > rg[i].first.second) {
			//cout << r <<" " <<e[r].first <<" "<< e[r].second << "\n";
			can = add(e[r].first, e[r].second);
			r--;
		}
		if(can) ans[rg[i].second] = 1;
	}
	for (auto i: ans) cout << (i ? "YES" : "NO") << "\n";
}
/*
6 8 5
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
1 8
1 3
1 6
1 2
1 4
*/

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:75:6: warning: unused variable 'l' [-Wunused-variable]
   75 |  int l, r;
      |      ^

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Incorrect	1 ms	348 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	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Incorrect	1 ms	348 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	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	150 ms	11656 KB	Output is correct
4	Correct	149 ms	12480 KB	Output is correct
5	Correct	138 ms	12736 KB	Output is correct
6	Correct	148 ms	11400 KB	Output is correct
7	Correct	149 ms	11200 KB	Output is correct
8	Correct	148 ms	9924 KB	Output is correct
9	Correct	129 ms	10688 KB	Output is correct
10	Correct	158 ms	12736 KB	Output is correct
11	Correct	131 ms	11208 KB	Output is correct
12	Correct	140 ms	12736 KB	Output is correct
13	Correct	132 ms	10172 KB	Output is correct
14	Correct	137 ms	10688 KB	Output is correct
15	Correct	138 ms	11972 KB	Output is correct
16	Correct	161 ms	12848 KB	Output is correct