답안 #929136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
929136	2024-02-17T18:32:47 Z	Joshua_Andersson	Joker (BOI20_joker)	C++14	0 / 100	2000 ms	6800 KB

Joker

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
const int inf = int(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }



struct UF
{
	vi size;
	vi par;
	vi parity;

	UF(int n) : size(n, 1), parity(n), par(n)
	{
		rep(i, n)par[i] = i;
	}

	int find(int x) { return x == par[x] ? x : find(par[x]); }
	int getparity(int x) { return x == par[x] ? parity[x] : parity[x] ^ getparity(par[x]); }
	bool oddcycle(int a, int b)
	{
		return getparity(a) == getparity(b);
	}

	void merge(int a, int b)
	{
		a = find(a); b = find(b);
		
		if (size[a] < size[b]) swap(a, b);

		if (a != b)
		{
			parity[b] ^= parity[a];
			size[a] += size[b];
			par[b] = a;
		}
	}
};

signed main()
{
	fast();

	int n, m, q;
	cin >> n >> m >> q;
	vector<p2> edgelist;
	rep(i, m)
	{
		int a, b;
		cin >> a >> b;
		a--; b--;
		edgelist.emplace_back(a, b);
	}

	while (q--)
	{
		int l, r;
		cin >> l >> r;
		l--; r--;
		UF uf(n);

		bool any = 0;
		rep(i, l)
		{
			int a, b;
			tie(a, b) = edgelist[i];
			if (uf.find(a)==uf.find(b)) any |= uf.oddcycle(a, b);
			uf.merge(a, b);
		}

		repp(i, r+1, m)
		{
			int a, b;
			tie(a, b) = edgelist[i];
			if (uf.find(a) == uf.find(b)) any |= uf.oddcycle(a, b);
			uf.merge(a, b);
		}
		cout << (any ? "YES" : "NO") << "\n";
	}

	return 0;
}

Compilation message

Joker.cpp: In constructor 'UF::UF(ll)':
Joker.cpp:25:5: warning: 'UF::parity' will be initialized after [-Wreorder]
   25 |  vi parity;
      |     ^~~~~~
Joker.cpp:24:5: warning:   'vi UF::par' [-Wreorder]
   24 |  vi par;
      |     ^~~
Joker.cpp:27:2: warning:   when initialized here [-Wreorder]
   27 |  UF(int n) : size(n, 1), parity(n), par(n)
      |  ^~

Subtask #1

0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Incorrect	1 ms	344 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #2

0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Incorrect	1 ms	344 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #3

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Execution timed out	2045 ms	6800 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #4

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Incorrect	1 ms	344 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #5

0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Incorrect	1 ms	344 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #6

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Incorrect	1 ms	344 KB	Output isn't correct
9	Halted	0 ms	0 KB	-