Submission #1298869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298869		flo	Joker (BOI20_joker)	C++20	Compilation error	0 ms	0 KiB

Joker

#include <bits/stdc++.h>
#define task "testing"
#define ll long long
#define multitest 0
using namespace std;

struct Edge {
	int u, v;
};

struct Queries {
	int l, r;
};

const int N = 2e5;

int n, m, q;

Edge E[2*N+5];

Queries Q[N+5];

bitset<N+5> res;

namespace sub12 {
	const int sN = 2e3;
	
	int dsu[2*sN+5];
	
	void reset() {
		fill(dsu+1, dsu+2*n+1, -1);
	}
	
	int root(int v) {
		return dsu[v] < 0 ? v : dsu[v] = root(dsu[v]);
	}
	
	void unite(int u, int v) {
		if ((u = root(u)) == (v = root(v))) return;
		
		if (dsu[u] > dsu[v]) swap(u, v);
		
		dsu[u] += dsu[v], dsu[v] = u;
	}
	
	bool connect(int u, int v) {
		return root(u) == root(v);
	}
	
	bool check() {
		return max({n, m, q}) <= sN;
	}
	
	bool qry(int l, int r) {
		reset();
		
		for (int x = l; x <= r; x++) {
			unite(E[x].u, E[x].v+n);
			unite(E[x].u+n, E[x].v);
		}
		
		for (int x = 1; x <= n; x++) {
			if (connect(x, x+n)) return 1;
		}
		
		return 0;
	}
	
	void solve() {
		for (int x = 1; x <= q; x++) {
			if (qry(Q[x].r+1, Q[x].l+m-1)) res.set(x);
		}
	}
}

namespace sub34 {
	const int L = 200;
	
	int dsu[2*N+5], rt[L+5], mxL;
	
	unordered_map<int, bool> st[2*N+5];
	
	bool check() {
		mxL = 0;
		
		for (int x = 1; x <= q; x++) {
			mxL = max(mxL, Q[x].l);
		}
		
		return mxL <= L;
	}
	
	int flip(int v) {
		return v+(v <= n ? n : -n);
	}
	
	void reset() {
		for (int x = 2*n; x >= 1; x--) {
			dsu[x] = -1, st[x].clear(), st[x][x] = 1;
		}
	}
	
	int root(int v) {
		return dsu[v] < 0 ? v : dsu[v] = root(dsu[v]);
	}
	
	bool unite(int u, int v) {
		if ((u = root(u)) == (v = root(v))) return 0;
		
		if (dsu[u] > dsu[v]) swap(u, v);
		
		dsu[u] += dsu[v], dsu[v] = u;
		
		for (auto x : st[v]) {
			if (st[u][flip(x)] == 1) return 1;
			
			st[u][x] = 1;
		}
		
		st[v].clear();
		
		return 0;
	}
	
	void calc(int l) {	
		reset();
		
		bool ex = 0;
		
		for (int x = 1; x < l && !ex; x++) {
			ex |= unite(E[x].u, E[x].v+n);
			ex |= unite(E[x].u+n, E[x].v);
		}
		
		if (ex) rt[l] = m+1;
		
		for (int r = m; r > l && !ex; r--) {
			ex |= unite(E[r].u, E[r].v+n);
			ex |= unite(E[r].u+n, E[r].v);
			
			if (ex) rt[l] = r;
		}
	}
	
	void solve() {
		for (int x = min(m, mxL); x >= 1; x--) calc(x);
		
		for (int x = 1; x <= q; x++) {
			if (Q[x].r < rt[Q[x].l]) res.set(x);
		}
	}
}

void flo(int ID) {
	cin >> n >> m >> q;
	
	for (int x = 1; x <= m; x++) {
		cin >> E[x].u >> E[x].v;
		
		E[x+m] = E[x];
	}
	
	for (int x = 1; x <= q; x++) {
		cin >> Q[x].l >> Q[x].r;
	}
	
	if (sub12::check()) sub12::solve();
	else if (sub34::check()) sub34::solve();
	
	for (int x = 1; x <= q; x++) {
		cout << (res.test(x) ? "YES\n" : "NO\n");
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

	int TCS = 1, ID = 1;

	if (multitest) {
		cin >> TCS;
	}

	while (TCS--) flo(ID++);

	return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'bool sub34::unite(int, int)':
Joker.cpp:115:40: error: cannot convert 'std::pair<const int, bool>' to 'int'
  115 |                         if (st[u][flip(x)] == 1) return 1;
      |                                        ^
      |                                        |
      |                                        std::pair<const int, bool>
Joker.cpp:93:22: note:   initializing argument 1 of 'int sub34::flip(int)'
   93 |         int flip(int v) {
      |                  ~~~~^
Joker.cpp:117:30: error: no match for 'operator[]' (operand types are 'std::unordered_map<int, bool>' and 'std::pair<const int, bool>')
  117 |                         st[u][x] = 1;
      |                              ^
In file included from /usr/include/c++/13/unordered_map:41,
                 from /usr/include/c++/13/functional:63,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53,
                 from Joker.cpp:1:
/usr/include/c++/13/bits/unordered_map.h:986:7: note: candidate: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type&) [with _Key = int; _Tp = bool; _Hash = std::hash<int>; _Pred = std::equal_to<int>; _Alloc = std::allocator<std::pair<const int, bool> >; mapped_type = bool; key_type = int]'
  986 |       operator[](const key_type& __k)
      |       ^~~~~~~~
/usr/include/c++/13/bits/unordered_map.h:986:34: note:   no known conversion for argument 1 from 'std::pair<const int, bool>' to 'const std::unordered_map<int, bool>::key_type&' {aka 'const int&'}
  986 |       operator[](const key_type& __k)
      |                  ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/unordered_map.h:990:7: note: candidate: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&&) [with _Key = int; _Tp = bool; _Hash = std::hash<int>; _Pred = std::equal_to<int>; _Alloc = std::allocator<std::pair<const int, bool> >; mapped_type = bool; key_type = int]'
  990 |       operator[](key_type&& __k)
      |       ^~~~~~~~
/usr/include/c++/13/bits/unordered_map.h:990:29: note:   no known conversion for argument 1 from 'std::pair<const int, bool>' to 'std::unordered_map<int, bool>::key_type&&' {aka 'int&&'}
  990 |       operator[](key_type&& __k)
      |                  ~~~~~~~~~~~^~~
Joker.cpp: In function 'int main()':
Joker.cpp:180:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |                 freopen(task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:181:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |                 freopen(task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~