oj.uz

Submission #54352

# Submission time Handle Problem Language Result Execution time Memory
54352 2018-07-03T08:03:04 Z 김세빈(#1473) Flood (IOI07_flood) C++11
100 / 100
 239 ms 21620 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair <int,int> pii;

vector <pii> G[202020];
queue <int> Q;
vector <int> P, W, V;
int X[101010], Y[101010], A[202020], B[202020];
int T[2202020], E[101010], D[101010];
bool chk[101010];
int n, m, cnt, max_x, max_y;

bool comp_P(int ca, int cb) { return X[ca] < X[cb]; }
bool comp_W(int ca, int cb) { return X[A[ca]] < X[A[cb]]; }

void update(int p, int s, int e, int l, int r, int v)
{
	if(e < l || r < s) return;
	if(l <= s && e <= r){
		T[p] = v;
		return;
	}
	
	if(T[p] != -1){
		T[p<<1] = T[p<<1|1] = T[p];
		T[p] = -1;
	}
	
	update(p<<1, s, s+e>>1, l, r, v);
	update(p<<1|1, (s+e>>1)+1, e, l, r, v);
}

int get_val(int p, int s, int e, int v)
{
	if(T[p] != -1) return T[p];
	
	if(v <= s+e>>1) return get_val(p<<1, s, s+e>>1, v);
	else return get_val(p<<1|1, (s+e>>1)+1, e, v);
}

void push(int p)
{
	Q.push(p);
	
	for(auto t: G[p]){
		if(!chk[t.first] && t.second == 0){
			D[t.first] = D[p];
			chk[t.first] = 1;
			push(t.first);
		}
	}
}

int main()
{
	int i, a, b, w, p, k, l, r;
	
	scanf("%d", &n);
	
	for(i=1;i<=n;i++){
		scanf("%d%d", X+i, Y+i);
		X[i] ++, Y[i] ++;
		P.push_back(i);
		
		max_x = max(max_x, X[i]);
		max_y = max(max_y, Y[i]);
	}
	
	scanf("%d", &m);
	
	for(i=1;i<=m;i++){
		scanf("%d%d", &a, &b);
		if(X[a] == X[b]){
			W.push_back(i);
			if(Y[a] > Y[b]) swap(a, b);
			A[i] = a, B[i] = b;
		}
		else{
			if(X[a] > X[b]) swap(a, b);
			E[a] = i;
		}
	}
	
	sort(P.begin(), P.end(), comp_P);
	sort(W.begin(), W.end(), comp_W);
	
	for(i=w=p=0;i<=max_x;i++){
		for(;w<W.size() && X[A[W[w]]] == i; w++){
			cnt ++;
			k = get_val(1, 0, max_y, Y[A[W[w]]]);
			
			G[k].push_back(pii(cnt, 1));
			G[cnt].push_back(pii(k, 1));
			
			update(1, 0, max_y, Y[A[W[w]]], Y[B[W[w]]] - 1, cnt);
			
			A[W[w]] = k, B[W[w]] = cnt;
		}
		for(;p<P.size() && X[P[p]] == i; p++){
			if(!E[P[p]]){
				l = get_val(1, 0, max_y, Y[P[p]] - 1);
				r = get_val(1, 0, max_y, Y[P[p]]);
				
				G[l].push_back(pii(r, 0));
				G[r].push_back(pii(l, 0));
			}
			else{
				l = get_val(1, 0, max_y, Y[P[p]] - 1);
				r = get_val(1, 0, max_y, Y[P[p]]);
				
				G[l].push_back(pii(r, 1));
				G[r].push_back(pii(l, 1));
				
				A[E[P[p]]] = l, B[E[P[p]]] = r;
			}
		}
	}
	
	chk[0] = 1;
	push(0);
	
	for(;Q.size();){
		p = Q.front(); Q.pop();
		for(auto t: G[p]){
			if(!chk[t.first]){
				D[t.first] = D[p] + 1;
				chk[t.first] = 1;
				push(t.first);
			}
		}
	}
	
	for(i=1;i<=m;i++){
		if(D[A[i]] == D[B[i]]){
			V.push_back(i);
		}
	}
	
	printf("%d\n", (int)V.size());
	
	for(auto t: V){
		printf("%d\n", t);
	}
	
	return 0;
}

Compilation message

flood.cpp: In function 'void update(int, int, int, int, int, int)':
flood.cpp:31:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  update(p<<1, s, s+e>>1, l, r, v);
                  ~^~
flood.cpp:32:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  update(p<<1|1, (s+e>>1)+1, e, l, r, v);
                  ~^~
flood.cpp: In function 'int get_val(int, int, int, int)':
flood.cpp:39:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(v <= s+e>>1) return get_val(p<<1, s, s+e>>1, v);
          ~^~
flood.cpp:39:43: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(v <= s+e>>1) return get_val(p<<1, s, s+e>>1, v);
                                          ~^~
flood.cpp:40:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else return get_val(p<<1|1, (s+e>>1)+1, e, v);
                               ~^~
flood.cpp: In function 'int main()':
flood.cpp:90:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;w<W.size() && X[A[W[w]]] == i; w++){
        ~^~~~~~~~~
flood.cpp:101:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;p<P.size() && X[P[p]] == i; p++){
        ~^~~~~~~~~
flood.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
flood.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", X+i, Y+i);
   ~~~~~^~~~~~~~~~~~~~~~~~
flood.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
flood.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5224 KB Output is correct
2 Correct 8 ms 5240 KB Output is correct
3 Correct 8 ms 5244 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5244 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5244 KB Output is correct
2 Correct 8 ms 5300 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5332 KB Output is correct
2 Correct 9 ms 5332 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5332 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5460 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5460 KB Output is correct
2 Correct 9 ms 5460 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5488 KB Output is correct
2 Correct 9 ms 5488 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9196 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 12744 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 15848 KB Output is correct
2 Correct 207 ms 21620 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 21620 KB Output is correct
2 Correct 206 ms 21620 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 21620 KB Output is correct
2 Correct 90 ms 21620 KB Output is correct