oj.uz

답안 #933592

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933592 2024-02-26T00:49:20 Z Joshua_Andersson Joker (BOI20_joker) C++14
25 / 100
 299 ms 28352 KB 
#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())
#define all(x) begin(x),end(x)
#define ceildiv(x,y) ((x + y - 1) / (y))

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

auto Start = chrono::high_resolution_clock::now();
void resettimer() { Start = chrono::high_resolution_clock::now(); }
int elapsedmillis() { return chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - Start).count(); }

#define _LOCAL _DEBUG
#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

struct change
{
	int a, b;
	int oldpar, oldxor, oldsize;
};

struct UF
{
	vector<change> updates;
	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)
	{
		if (size[find(a)] < size[find(b)]) swap(a, b);
		int childa = a;
		int childb = b;
		a = find(a); b = find(b);
		change c({ a,b,par[b],parity[b],size[a] });
		updates.push_back(c);

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

	void rollback()
	{
		change c = updates.back();
		updates.pop_back();
		par[c.b] = c.oldpar;
		parity[c.b] = c.oldxor;
		size[c.a] = c.oldsize;
	}
};

UF uf(0);
vector<p2> edgelist;
bool add(int i)
{
	int a, b;
	tie(a, b) = edgelist[i];
	int ret = 0;
	if (uf.find(a) == uf.find(b)) ret = uf.oddcycle(a, b);
	uf.merge(a, b);
	return ret;
};

vi rightp;
void dc(int l, int r, int hr, bool yes) // we have added edges [0,i) and (r, M)
{
	if (l==r)
	{
		//cout << l << ": " << hr << "\n";
		rightp[l] = (yes ? inf : hr);
		return;
	}
	int mid = (l + r) / 2;


	// left side
	// update hr
	repp(i, l, mid) add(i);

	int cnt = 0;
	int newhr = -1;
	for (int i = hr; i >= mid; i--)
	{
		cnt++;
		if (add(i))
		{
			newhr = i;
			break;
		}
	}
	rep(i, cnt) uf.rollback();
	repp(i, l, mid) uf.rollback();

	for (int i = hr, j = cnt-1; j > 0; i--, j--) add(i);
	dc(l, mid, newhr, yes);
	rep(i, cnt-1) uf.rollback();
	
	// right side
	bool newyes = 0;
	int newhl = newhr;
	repp(i, l, mid+1) newyes |= add(i);
	dc(mid + 1, r, hr, newyes);

	repp(i, l, mid+1) uf.rollback();

}

signed main()
{
	fast();

	int n, m, q;
	cin >> n >> m >> q;
	edgelist;
	rep(i, m)
	{
		int a, b;
		cin >> a >> b;
		a--; b--;
		edgelist.emplace_back(a, b);
	}
	//shuffle(edgelist.begin(), prev(edgelist.end()), mt19937(3436876));

	uf = UF(n);

	/*vi right(m, inf);
	bool anyodd = 0;

	rep(i, m)
	{
		int lo = i;
		int hi = m;
		while (lo + 1 < hi)
		{
			int mid = (lo + hi) / 2;
			bool odd = 0;
			for (int j = m - 1; j >= mid; j--) odd |= add(j);
			for (int j = m - 1; j >= mid; j--) uf.rollback();
			if (odd) lo = mid;
			else hi = mid;
		}
		right[i] = lo;

		if (anyodd) right[i] = inf;
		anyodd |= add(i);
	}*/
	uf = UF(n);
	rightp.resize(m);
	dc(0, m-1, m-1, 0);

	//vvi queries(m);
	while (q--)
	{
		int l, r;
		cin >> l >> r;
		l--; r--;

		cout << (r + 1 <= rightp[l] ? "YES" : "NO") << "\n";
	}

	return 0;
}

Compilation message

Joker.cpp: In constructor 'UF::UF(ll)':
Joker.cpp:41:5: warning: 'UF::parity' will be initialized after [-Wreorder]
   41 |  vi parity;
      |     ^~~~~~
Joker.cpp:40:5: warning:   'vi UF::par' [-Wreorder]
   40 |  vi par;
      |     ^~~
Joker.cpp:43:2: warning:   when initialized here [-Wreorder]
   43 |  UF(int n) : size(n, 1), parity(n), par(n)
      |  ^~
Joker.cpp: In function 'void dc(ll, ll, ll, bool)':
Joker.cpp:130:6: warning: unused variable 'newhl' [-Wunused-variable]
  130 |  int newhl = newhr;
      |      ^~~~~
Joker.cpp: In function 'int main()':
Joker.cpp:144:2: warning: statement has no effect [-Wunused-value]
  144 |  edgelist;
      |  ^~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 178 ms 24180 KB Output is correct
4 Correct 161 ms 28352 KB Output is correct
5 Correct 190 ms 26664 KB Output is correct
6 Correct 213 ms 24496 KB Output is correct
7 Correct 224 ms 24492 KB Output is correct
8 Correct 266 ms 24252 KB Output is correct
9 Correct 269 ms 24500 KB Output is correct
10 Correct 298 ms 27420 KB Output is correct
11 Correct 227 ms 24628 KB Output is correct
12 Correct 257 ms 26808 KB Output is correct
13 Correct 256 ms 23604 KB Output is correct
14 Correct 267 ms 23256 KB Output is correct
15 Correct 294 ms 25520 KB Output is correct
16 Correct 299 ms 28344 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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