oj.uz

답안 #926283

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
926283 2024-02-12T18:17:05 Z mansur Joker (BOI20_joker) C++17
25 / 100
 189 ms 28108 KB 
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
 
#include<bits/stdc++.h>	
 
using namespace std;
 
#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()                 
#define sz(a) (int)a.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
     
vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
 
const int N = 1e6 + 1, mod = 998244353;
 
const ll inf = 1e9;
 
double eps = 1e-15;
                                                
bool flg = 0;
 
bool ok = 1, was[N];
vector<pii> g(N);
 
int p[N], pr[N];
int sz[N], pt[N];
vector<pii> h;
 
pii get(int x) {
 	if (p[x] == x) return {x, 0};
 	pii val = get(p[x]);
 	return {val.f, ((pr[x] + val.s) & 1)};
}
 
inline void add(int id) {
	int u = g[id].f;
	int v = g[id].s;
	pii x = get(u);
	pii y = get(v);
	if (x.f == y.f) {
		if (x.s == y.s) {
			if (ok) {
			    h.push_back({-1, -1});
				ok = 0;
			}    
		}
		return;
	}
	if (sz[x.f] > sz[y.f]) swap(x, y);
	h.push_back({x.f, sz[x.f]});
	h.push_back({y.f, sz[y.f]});
	p[x.f] = y.f;
	pr[x.f] = ((x.s + y.s + 1) & 1);  	
	sz[y.f] += sz[x.f];
}
 
inline void rb() {
	while (sz(h) && !pt[sz(h)]) {
		pii x = h.back();
		h.pop_back();
		if (x.f == -1) {
			ok = 1;
			continue;
		}
		p[x.f] = x.f;
		pr[x.f] = 0;
		sz[x.f] = x.s;
	}
	pt[sz(h)]--; 
}
 
int ps[N];
 
void f(int l, int r, int tr) {
	if (l > r) return;
	int m = (l + r) / 2;
	pt[sz(h)]++;
	for (int i = m - 1; i >= l; i--) 
		add(i);
	pt[sz(h)]++;
	if (!ok) ps[m] = tr + 1;
	for (int i = tr; ok && i > m; i--) {
		add(i);
		if (!ok) {
			ps[m] = i;
			break;
		}
	}
	rb();
	add(m);
	f(m + 1, r, tr);
	rb();
	if (!ps[m]) return;
	pt[sz(h)]++;
	for (int i = tr; i > ps[m]; i--)
		add(i);
	f(l, m - 1, ps[m]);
	rb();
}
 
void slv() {
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		g[i] = {u, v};
	}
	for (int i = 1; i <= n; i++) 
		p[i] = i, sz[i] = 1;
	f(1, m, m);
	for (int i = 1; i <= q; i++) {
		int l, r;
		cin >> l >> r;
		if (ps[l] > r) cout << "YES\n";
		else cout << "NO\n";
	}
}                                                                           
 
main() {
	//freopen("rsq.in", "r", stdin);                                                                                     
	//freopen("rsq.out", "w", stdout);                                                                                     
	ios_base::sync_with_stdio(0);	                                                                                       
	cin.tie(0);
	int tp = 1;
	if (flg) cin >> tp;
	while (tp--) {  	
		slv();
	}
}

Compilation message

Joker.cpp:129:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  129 | main() {
      | ^~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16472 KB Output is correct
2 Correct 3 ms 16472 KB Output is correct
3 Correct 120 ms 21032 KB Output is correct
4 Correct 70 ms 25568 KB Output is correct
5 Correct 124 ms 26344 KB Output is correct
6 Correct 120 ms 21448 KB Output is correct
7 Correct 131 ms 21304 KB Output is correct
8 Correct 136 ms 21040 KB Output is correct
9 Correct 138 ms 21336 KB Output is correct
10 Correct 178 ms 27072 KB Output is correct
11 Correct 145 ms 21232 KB Output is correct
12 Correct 151 ms 25804 KB Output is correct
13 Correct 131 ms 19680 KB Output is correct
14 Correct 126 ms 20416 KB Output is correct
15 Correct 189 ms 22760 KB Output is correct
16 Correct 184 ms 28108 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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