oj.uz

Submission #121279

# Submission time Handle Problem Language Result Execution time Memory
121279 2019-06-26T09:37:35 Z WhipppedCream Flood (IOI07_flood) C++17
55 / 100
 63 ms 19288 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e5+5;

vector<int> allx, ally;

int px[maxn], py[maxn];

void dup(vector<int> &foo)
{
	sort(foo.begin(), foo.end());
	foo.resize(unique(foo.begin(), foo.end())-foo.begin());
}

const int maxl = 1005;

int dist[maxl][maxl];
bool ban[maxl][maxl][4];

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int wu[maxn], wv[maxn];

int main()
{
	int n; scanf("%d", &n);
	for(int i = 1; i<= n; i++)
	{
		scanf("%d %d", &px[i], &py[i]);
		allx.pb(px[i]); ally.pb(py[i]);
	}
	dup(allx); dup(ally);
	for(int i = 1; i<= n; i++)
	{
		px[i] = lower_bound(allx.begin(), allx.end(), px[i])-allx.begin()+1;
		py[i] = lower_bound(ally.begin(), ally.end(), py[i])-ally.begin()+1;
	}
	int m; scanf("%d", &m);
	for(int i = 1; i<= m; i++)
	{
		int u, v; scanf("%d %d", &u, &v);
		wu[i] = u; wv[i] = v;
		if(px[u] == px[v])
		{
			if(py[u]> py[v]) swap(u, v);
			for(int i = py[u]; i< py[v]; i++)
			{
				ban[px[u]-1][i][0] = true;
				ban[px[u]][i][2] = true;
			}
		}
		if(py[u] == py[v])
		{
			if(px[u]> px[v]) swap(u, v);
			for(int i = px[u]; i< px[v]; i++)
			{
				ban[i][py[u]-1][1] = true;
				ban[i][py[u]][3] = true;
			}
		}
	}
	int a = allx.size()+5;
	int b = ally.size()+5;
	for(int i = 0; i<= a; i++) for(int j = 0; j<= b; j++) dist[i][j] = 1e9;
	priority_queue< pair<int, ii> > pq; pq.push({0, {0, 0}});
	dist[0][0] = 0;
	while(!pq.empty())
	{
		auto kk = pq.top(); pq.pop();
		int d = -kk.X;
		int x = kk.Y.X, y = kk.Y.Y;
		// printf("from %d %d\n", x, y);
		if(d> dist[x][y]) continue;
		for(int i = 0; i< 4; i++)
		{
			int nx = x+dx[i], ny = y+dy[i];
			if(nx< 0 || nx>a || ny< 0 || ny> b) continue;
			// printf("prob %d %d\n", nx, ny);
			if(dist[nx][ny]> ban[x][y][i]+dist[x][y])
			{
				dist[nx][ny] = ban[x][y][i]+dist[x][y];
				pq.push({-dist[nx][ny], {nx, ny}});
			}
		}
	}
	vector<int> res;
	for(int i = 1; i<= m; i++)
	{
		int u = wu[i], v = wv[i];
		if(px[u] == px[v])
		{
			if(py[u]> py[v]) swap(u, v);
			if(dist[px[u]-1][py[u]] == dist[px[u]][py[u]]) res.pb(i);
		}
		if(py[u] == py[v])
		{
			if(px[u]> px[v]) swap(u, v);
			if(dist[px[u]][py[u]-1] == dist[px[u]][py[u]]) res.pb(i);
		}
	}
	printf("%d\n", (int) res.size());
	for(int x : res) printf("%d\n", x);
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n);
         ~~~~~^~~~~~~~~~
flood.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &px[i], &py[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int m; scanf("%d", &m);
         ~~~~~^~~~~~~~~~
flood.cpp:50:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 2 ms 640 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 768 KB Output is correct
2 Correct 2 ms 556 KB Output is correct

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1536 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2048 KB Output is correct
2 Correct 4 ms 1024 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 2176 KB Output isn't correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 19288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 4096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 4332 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -