oj.uz

Submission #871021

# Submission time Handle Problem Language Result Execution time Memory
871021 2023-11-09T17:42:14 Z NaimSS Joker (BOI20_joker) C++14
0 / 100
 1753 ms 33472 KB 
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define pb push_back
#define ld long double
#define ff first
#define ss second
#define endl '\n'
#define sz(v) ((int)v.size())
#define all(v) begin(v),end(v)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

void dbg_out() { cerr << endl ;}
template<typename Head, typename... Tail> void dbg_out(Head H,Tail... T){
	cerr<<' '<<H ;
	dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr<<"("<< #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__), cerr << endl;
#else 
#define dbg(...) 42
#endif

struct event{
	int a,b,psb,pa,is_good;
	event(int a,int b,int psb,int pa,int is_good):
	a(a),b(b),psb(psb),pa(pa),is_good(is_good){}
};

struct DSU{
	vector<event> st;
	int is_good;
	int n;
	vi p,ps,ar;
	DSU(int n):n(n){
		p = ps = vi(n+1,1);
		ar = vi(n+1,0);
		rep(i,0,n+1)p[i] = i;
		is_good = 1;
	}
	pii find(int x){
		int val=0;
		while(x!=p[x]){
			val^=ar[x];
			x = p[x];
		}
		return pii(x,val);
	}
	int f(int x){return find(x).ff;}
	int cor(int x){return find(x).ss;}
	bool join(int a,int b){
		int ca = cor(a),cb = cor(b);
		a = f(a),b = f(b);
		if(a == b){
			st.pb(event(a,b,ps[b],p[a],is_good));
			if(ca == cb){
				is_good = 0;
			}
			return 0;	
		}
		if(ps[a] > ps[b])swap(a,b);
		st.pb(event(a,b,ps[b],p[a],is_good));
		ps[b] += ps[a], p[a] = b;
		return 1;
	}
	void undo(){
		auto [a,b,psb,pa,Isgood] = st.back();
		p[a] = pa,ps[b] = psb,is_good = Isgood;
		st.pop_back();
	}
	void clear(){
		while(sz(st))undo();
	}
	int ok(){return is_good;}
};

const int N = 2 * (200100);
const int SQ = 400;
int a[N], b[N];
struct query{
	int l,r,id;
	query(int l,int r,int id):l(l),r(r),id(id){}
};
vector<query> Q[N];
int res[N];
int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,m,q;
	cin >> n >> m >> q;
	rep(i,1,m+1){
		cin >> a[i] >> b[i];
		a[i + m] = a[i], b[i+m] = b[i];
	}
	rep(i,1,q+1){
		int l,r;
		cin >> l >> r;
		if( l == 1 && r == m){
			res[i] = 1;
			continue;
		}
		Q[(r+1)/SQ].pb(query(r+1,l+m-1,i));
	}
	DSU d(n);
	for(int bk=0;bk<N;bk++){
		if(sz(Q[bk])==0)continue;
		d.clear();
		sort(all(Q[bk]),[&](query a,query b){
			return a.r < b.r;
		});

		int ptr = (bk + 1) * SQ;
		int lB = ptr - 1;
		for(auto q : Q[bk]){
			int l = q.l,r = q.r;
			while(ptr <= r){
				d.join(a[ptr], b[ptr]);
				ptr++;
			}
			int qtd=0;
			for(int i=min(r,lB);i >= l; i--){
				d.join(a[i], b[i]);
				qtd++;
			}
			res[q.id] = d.ok();
			while(qtd--)d.undo();
		}
	}
	rep(i,1,q+1){
		cout << (res[i] == 1 ? "NO" : "YES") << endl; 
	}
	
}

Compilation message

Joker.cpp: In member function 'void DSU::undo()':
Joker.cpp:71:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |   auto [a,b,psb,pa,Isgood] = st.back();
      |        ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 4 ms 12740 KB Output is correct
3 Correct 3 ms 12784 KB Output is correct
4 Correct 3 ms 12632 KB Output is correct
5 Correct 4 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Incorrect 4 ms 12636 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 4 ms 12740 KB Output is correct
3 Correct 3 ms 12784 KB Output is correct
4 Correct 3 ms 12632 KB Output is correct
5 Correct 4 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Incorrect 4 ms 12636 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 4 ms 12740 KB Output is correct
3 Correct 1173 ms 27628 KB Output is correct
4 Incorrect 1753 ms 33472 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 4 ms 12740 KB Output is correct
3 Correct 3 ms 12784 KB Output is correct
4 Correct 3 ms 12632 KB Output is correct
5 Correct 4 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Incorrect 4 ms 12636 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 4 ms 12740 KB Output is correct
3 Correct 3 ms 12784 KB Output is correct
4 Correct 3 ms 12632 KB Output is correct
5 Correct 4 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Incorrect 4 ms 12636 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 4 ms 12740 KB Output is correct
3 Correct 3 ms 12784 KB Output is correct
4 Correct 3 ms 12632 KB Output is correct
5 Correct 4 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Incorrect 4 ms 12636 KB Output isn't correct
9 Halted 0 ms 0 KB -