oj.uz

Submission #54346

# Submission time Handle Problem Language Result Execution time Memory
54346 2018-07-03T07:55:03 Z 김세빈(#1473) Flood (IOI07_flood) C++11
0 / 100
 862 ms 33792 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair <int,int> pii;

vector <int> P[1010101], W[1010101];
vector <pii> G[202020];
queue <int> Q;
vector <int> 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;

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, 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[X[i]].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[X[a]].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;
		}
	}
	
	for(i=0;i<=max_x;i++){
		for(auto t: W[i]){
			cnt ++;
			k = get_val(1, 0, max_y, Y[A[t]]);
			
			G[k].push_back(pii(cnt, 1));
			G[cnt].push_back(pii(k, 1));
			
			update(1, 0, max_y, Y[A[t]], Y[B[t]] - 1, cnt);
			
			A[t] = k, B[t] = cnt;
		}
		for(auto t: P[i]){
			if(!E[t]){
				l = get_val(1, 0, max_y, Y[t]-1);
				r = get_val(1, 0, max_y, Y[t]);
				
				G[l].push_back(pii(r, 0));
				G[r].push_back(pii(l, 0));
			}
			else{
				l = get_val(1, 0, max_y, Y[t]-1);
				r = get_val(1, 0, max_y, Y[t]);
				
				G[l].push_back(pii(r, 1));
				G[r].push_back(pii(l, 1));
				
				A[E[t]] = l, B[E[t]] = 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:29:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  update(p<<1, s, s+e>>1, l, r, v);
                  ~^~
flood.cpp:30: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:37:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(v <= s+e>>1) return get_val(p<<1, s, s+e>>1, v);
          ~^~
flood.cpp:37:43: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(v <= s+e>>1) return get_val(p<<1, s, s+e>>1, v);
                                          ~^~
flood.cpp:38: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:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
flood.cpp:61: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:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
flood.cpp:72: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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 149 ms 33792 KB Memory limit exceeded

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 156 ms 33792 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 153 ms 33792 KB Memory limit exceeded

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 33792 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 131 ms 33792 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 227 ms 33792 KB Memory limit exceeded

Subtask #7
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 240 ms 33792 KB Memory limit exceeded

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 205 ms 33792 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 207 ms 33792 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 291 ms 33792 KB Memory limit exceeded

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 422 ms 33792 KB Memory limit exceeded

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 567 ms 33792 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 862 ms 33792 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 821 ms 33792 KB Memory limit exceeded
2 Halted 0 ms 0 KB -