oj.uz

답안 #933598

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933598 2024-02-26T01:07:56 Z Joshua_Andersson Joker (BOI20_joker) C++14
25 / 100
 329 ms 25040 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 = hr;
	for (int i = hr; i >= mid; i--)
	{
		cnt++;
		newhr = i;
		if (add(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();

	//ifstream in("C:\\Users\\Matis\\Desktop\\comp_prog\\x64\\debug\\in.txt");
	//cin.rdbuf(in.rdbuf());

	int n, m, q;
	cin >> n >> m >> q;

	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);
	//assert(right == rightp);
	//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;
      |      ^~~~~

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 0 ms 344 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 0 ms 344 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 193 ms 23112 KB Output is correct
4 Correct 282 ms 23644 KB Output is correct
5 Correct 155 ms 23392 KB Output is correct
6 Correct 217 ms 20628 KB Output is correct
7 Correct 228 ms 22016 KB Output is correct
8 Correct 286 ms 20232 KB Output is correct
9 Correct 278 ms 21980 KB Output is correct
10 Correct 305 ms 25040 KB Output is correct
11 Correct 232 ms 20656 KB Output is correct
12 Correct 251 ms 22192 KB Output is correct
13 Correct 253 ms 19996 KB Output is correct
14 Correct 273 ms 19828 KB Output is correct
15 Correct 313 ms 21828 KB Output is correct
16 Correct 329 ms 24760 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 0 ms 344 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 0 ms 344 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 0 ms 344 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -