oj.uz

Submission #362939

# Submission time Handle Problem Language Result Execution time Memory
362939 2021-02-04T18:57:38 Z songc Joker (BOI20_joker) C++14
0 / 100
 2000 ms 14552 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define Mup(a,x) a=max(a, x)
#define mup(a,x) a=min(a, x)
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define INF (1ll<<60)
#define MOD 1'000'000'007 
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M, Q;
int U[202020], V[202020];
int P[404040], R[202020];
vector<pii> rb;

int rt(int u){
	if (P[u] < 0) return u;
	return rt(P[u]);
}

void uni(int u, int v){
	u = rt(u), v = rt(v);
	if (u == v) return;
	if (P[u] > P[v]) swap(u, v);
	rb.pb(pii(u, P[u]));
	rb.pb(pii(v, P[v]));
	P[u] += P[v], P[v] = u;
}

void undo(){
	pii t = rb.back();
	rb.pop_back();
	P[t.fi] = t.se;
}

void dnc(int s, int e, int r){
	if (s > e) return;
	int m=s+e>>1, rs=rb.size();
	for (int i=max(s,1); i<=m; i++){
		uni(U[i], V[i]+N);
		uni(U[i]+N, V[i]);
		if (rt(U[i]) == rt(U[i]+N)){
			for (int j=m; j<=e; j++) R[j] = r;
			while (rb.size()>rs) undo();
			dnc(s, m-1, r);
			return;
		}
	}
	int rr=rb.size();
	for (int i=r-1; i>s; i--){
		uni(U[i], V[i]+N);
		uni(U[i]+N, V[i]);
		if (rt(U[i]) == rt(U[i]+N)){R[m] = i; break;}
	}
	while (rb.size()>rr) undo();
	dnc(m+1, e, r);
	while (rb.size()>rs) undo();
	for (int i=r-1; i>=max(R[i],1); i--){
		uni(U[i], V[i]+N);
		uni(U[i]+N, V[i]);
		if (rt(U[i]) == rt(U[i]+N)){
			for (int j=s; j<m; j++) R[j] = R[m];
			return;
		}
	}
	dnc(s, m-1, R[m]);
}

int main(){
	scanf("%d %d %d", &N, &M, &Q);
	for (int i=1; i<=M; i++) scanf("%d %d", &U[i], &V[i]);
	for (int i=1; i<=2*N; i++) P[i] = -1;
	dnc(0, M-1, M+1);
	while (Q--){
		int l, r;
		scanf("%d %d", &l, &r);
		puts(r<R[l-1]?"YES":"NO");
	}
	return 0;
}

Compilation message

Joker.cpp: In function 'void dnc(int, int, int)':
Joker.cpp:42:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |  int m=s+e>>1, rs=rb.size();
      |        ~^~
Joker.cpp:48:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |    while (rb.size()>rs) undo();
      |           ~~~~~~~~~^~~
Joker.cpp:59:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |  while (rb.size()>rr) undo();
      |         ~~~~~~~~~^~~
Joker.cpp:61:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |  while (rb.size()>rs) undo();
      |         ~~~~~~~~~^~~
Joker.cpp: In function 'int main()':
Joker.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |  scanf("%d %d %d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:75:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |  for (int i=1; i<=M; i++) scanf("%d %d", &U[i], &V[i]);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |   scanf("%d %d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 236 ms 11348 KB Output is correct
4 Correct 297 ms 14552 KB Output is correct
5 Execution timed out 2094 ms 14296 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -