답안 #858300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
858300	2023-10-08T04:34:33 Z	Trisanu_Das	Joker (BOI20_joker)	C++17	컴파일 오류	0 ms	0 KB

Joker

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define ff first
#define ss second

const int N = 200100;
int dsu[2 * N];
int sz[2 * N];
bool is_bipar = true;
vector<tuple<int, int, int, int>> ba;
vector<bool> bipar;
 
 
inline int find(int x) {
	while (x != dsu[x]) x = dsu[x];
	return x;
}
 
inline void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (sz[a] < sz[b]) swap(a, b);
	if (a == b) return;
	bipar.pb(is_bipar);
	ba.eb(a, sz[a], b, dsu[b]);
	dsu[b] = a;
	sz[a] += sz[b];
}
 
bool same(int a, int b) {
	return find(a) == find(b);
}
 
void merge(int a, int b) {
	unite(a, b + N);
	unite(b, a + N);
	if (same(a, a + N) || same(b, b + N)) is_bipar = false;
}
 
void back() {
	int a, b, c, d;
	tie(a, b, c, d) = ba.back();
	sz[a] = b;
	dsu[c] = d;
	is_bipar = bipar.back();
	ba.pop_back();
	bipar.pop_back();
}
 
void init() {
	for(int i = 0; i < 2 * N; i++) {
		dsu[i] = i;
		sz[i] = 1;
	}
}
 
bool ans[N];
 
struct Q {
	int l, r, i;
};
 
bool operator<(Q a, Q b) {
	return a.r > b.r;
}
 
vector<Q> qu[N];
 
int main() {
	bipar.reserve(2 * N);
	ba.reserve(2 * N);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	vpii edges;
	for(int i = 0; i < m ; i++){
		int u, v;
		cin >> u >> v;
		edges.pb(u, v);
	}
	const int K = 2000;
	for(int i = 0; i < q; i++){
		int l, r;
		cin >> l >> r;
		l--; r--;
		qu[l / K].pb({ l, r, i });
	}
	init();
	for(int bl = 0; bl < N; bl++){
		int bl_l = bl * K;
		int bl_r = min((bl + 1) * K - 1, m - 1);
		if (qu[bl].size()) {
			sort(qu[bl].begin, qu[bl].end());
			int pr = m - 1;
			int was_on_start = ba.size();
			for(int j = 0; j < qu[bl.size(); j++){
				while (pr > qu[bl][j].r) {
					int v1 = edges[pr].ff;
					int v2 = edges[pr].ss;
					pr--;
					merge(v1, v2);
				}
				int was = ba.size();
				for (int i = qu[bl][j].l - 1; i >= bl_l; i--) {
					int v1 = edges[i].ff;
					int v2 = edges[i].ss;
					merge(v1, v2);
				}
				ans[qu[bl][j].i] = is_bipar;
				while (ba.size() != was) back();
			}
 
			while (ba.size() != was_on_start) back();
		}
		for (int i = bl_l; i <= bl_r; i++) {
			int v1 = edges[i].ff;
			int v2 = edges[i].ss;
			merge(v1, v2);
		}
	}
 
	for(int i = 0; i < q; i++){
		if (ans[i]) cout << "NO\n";
		else cout << "YES\n";
	}
}

Compilation message

Joker.cpp: In function 'void unite(int, int)':
Joker.cpp:27:5: error: 'class std::vector<std::tuple<int, int, int, int> >' has no member named 'eb'
   27 |  ba.eb(a, sz[a], b, dsu[b]);
      |     ^~
Joker.cpp: In function 'int main()':
Joker.cpp:78:2: error: 'vpii' was not declared in this scope
   78 |  vpii edges;
      |  ^~~~
Joker.cpp:82:3: error: 'edges' was not declared in this scope
   82 |   edges.pb(u, v);
      |   ^~~~~
Joker.cpp:96:35: error: no matching function for call to 'sort(<unresolved overloaded function type>, std::vector<Q>::iterator)'
   96 |    sort(qu[bl].begin, qu[bl].end());
      |                                   ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Joker.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:4849:5: note: candidate: 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Q*, std::vector<Q> >]'
 4849 |     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~
/usr/include/c++/10/bits/stl_algo.h:4849:32: note:   no known conversion for argument 1 from '<unresolved overloaded function type>' to '__gnu_cxx::__normal_iterator<Q*, std::vector<Q> >'
 4849 |     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |          ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
/usr/include/c++/10/bits/stl_algo.h:4880:5: note: candidate: 'template<class _RAIter, class _Compare> void std::sort(_RAIter, _RAIter, _Compare)'
 4880 |     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
      |     ^~~~
/usr/include/c++/10/bits/stl_algo.h:4880:5: note:   template argument deduction/substitution failed:
Joker.cpp:96:35: note:   candidate expects 3 arguments, 2 provided
   96 |    sort(qu[bl].begin, qu[bl].end());
      |                                   ^
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Joker.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:292:1: note: candidate: 'template<class _ExecutionPolicy, class _RandomAccessIterator, class _Compare> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> std::sort(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Compare)'
  292 | sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp);
      | ^~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:292:1: note:   template argument deduction/substitution failed:
Joker.cpp:96:35: note:   candidate expects 4 arguments, 2 provided
   96 |    sort(qu[bl].begin, qu[bl].end());
      |                                   ^
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Joker.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:296:1: note: candidate: 'template<class _ExecutionPolicy, class _RandomAccessIterator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void> std::sort(_ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator)'
  296 | sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last);
      | ^~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:296:1: note:   template argument deduction/substitution failed:
Joker.cpp:96:35: note:   candidate expects 3 arguments, 2 provided
   96 |    sort(qu[bl].begin, qu[bl].end());
      |                                   ^
Joker.cpp:99:29: error: request for member 'size' in 'bl', which is of non-class type 'int'
   99 |    for(int j = 0; j < qu[bl.size(); j++){
      |                             ^~~~
Joker.cpp:99:35: error: expected ']' before ';' token
   99 |    for(int j = 0; j < qu[bl.size(); j++){
      |                                   ^
      |                                   ]
Joker.cpp:101:15: error: 'edges' was not declared in this scope
  101 |      int v1 = edges[pr].ff;
      |               ^~~~~
Joker.cpp:108:15: error: 'edges' was not declared in this scope
  108 |      int v1 = edges[i].ff;
      |               ^~~~~
Joker.cpp:113:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |     while (ba.size() != was) back();
      |            ~~~~~~~~~~^~~~~~
Joker.cpp:116:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  116 |    while (ba.size() != was_on_start) back();
      |           ~~~~~~~~~~^~~~~~~~~~~~~~~
Joker.cpp:119:13: error: 'edges' was not declared in this scope
  119 |    int v1 = edges[i].ff;
      |             ^~~~~