Submission #121279

#	Time	Username	Problem	Language	Result	Execution time	Memory
121279		WhipppedCream	Flood (IOI07_flood)	C++17	55 / 100	63 ms	19288 KiB

flood

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9