Submission #121257

#	Time	Username	Problem	Language	Result	Execution time	Memory
121257		WhipppedCream	Flood (IOI07_flood)	C++17	0 / 100	299 ms	29476 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;
const int maxm = 2e5+5;

vector< ii > pts[maxn];
map< ii, int> rev;

int n, m;
int px[maxn], py[maxn];
int wu[maxm], wv[maxm];

int used[2*maxm];

int detdir(int u, int v)
{
	if(px[u] == px[v])
	{
		if(py[u]< py[v]) return 1;
		return 3;
	}
	if(px[u]< px[v]) return 0;
	return 2;
}

int yep[2*maxm];

void trav(int u, int from, int dir, int face)
{
	if(u == from) return;
	ii out[4];
	for(int i = 0; i< 4; i++) out[i] = {-1, -1};
	for(auto kk : pts[u])
	{
		int v = kk.X, id = kk.Y;
		out[(detdir(u, v)+1-dir+4)%4] = kk;
	}
	int st = -1;
	for(int i = 0; i< 4; i++)
	{
		int v = out[i].X, id = out[i].Y;
		if(v == -1) continue;
		if(used[id]) continue;
		st = i;
		break;
	}
	int v = out[st].X, id = out[st].Y;
	used[id] = true;
	yep[id] = face;
	// printf("(%d, %d)-(%d)->(%d, %d)\n", px[u], py[u], id, px[v], py[v]);
	trav(v, from, detdir(u, v), face);
}

vector<int> adj[2*maxm];

int dist[2*maxn];

int main()
{
	scanf("%d", &n);
	for(int i = 1; i<= n; i++)
	{
		scanf("%d %d", &px[i], &py[i]);
		rev[ii(px[i], py[i])] = i;
	}
	px[n+1] = -1; py[n+1] = -1;
	px[n+2] = -1; py[n+2] = 1e6+5;
	px[n+3] = 1e6+5; py[n+3] = -1;
	px[n+4] = 1e6+5; py[n+4] = 1e6+5;
	scanf("%d", &m);
	for(int i = 1; i<= m; i++)
	{
		scanf("%d %d", &wu[i], &wv[i]);
	}
	wu[m+1] = n+1; wv[m+1] = n+2;
	wu[m+2] = n+2; wv[m+2] = n+3;
	wu[m+3] = n+3; wv[m+3] = n+4;
	wu[m+4] = n+4; wv[m+4] = n+1;
	m += 4;
	for(int i = 1; i<= m; i++)
	{
		pts[wu[i]].pb(ii(wv[i], 2*i-1));
		pts[wv[i]].pb(ii(wu[i], 2*i));
	}
	int cc = 0;
	for(int i = 1; i<= 2*m; i++)
	{
		if(used[i]) continue;
		int u = wu[(i+1)/2], v = wv[(i+1)/2];
		if(i%2 == 0) swap(u, v);
		cc++;
		// printf("%d\n", cc);
		used[i] = true;
		yep[i] = cc;
		trav(v, u, detdir(u, v), cc);
	}
	for(int i = 1; i<= m; i++)
	{
		adj[yep[2*i-1]].pb(yep[2*i]);
		adj[yep[2*i]].pb(yep[2*i-1]);
		// printf("%d---%d\n", yep[2*i-1], yep[2*i]);
	}
	for(int i = 1; i<= cc; i++) dist[i] = 1e9;
	queue<int> q;
	q.push(yep[2*m]); dist[yep[2*m]] = 0;
	while(!q.empty())
	{
		int u = q.front(); q.pop();	
		for(int v : adj[u])
		{
			if(dist[v]> dist[u]+1)
			{
				dist[v] = dist[u]+1;
				q.push(v);
			}
		}
	}
	vector<int> res;
	for(int i = 1; i<= m-4; i++)
	{
		if(yep[2*i-1] == yep[2*i])
		{
			res.pb(i);
		}
	}
	printf("%d\n", res.size());
	sort(res.begin(), res.end());
	for(int x : res) printf("%d\n", x);
}

Compilation message (stderr)

flood.cpp: In function 'void trav(int, int, int, int)':
flood.cpp:43:17: warning: unused variable 'id' [-Wunused-variable]
   int v = kk.X, id = kk.Y;
                 ^~
flood.cpp: In function 'int main()':
flood.cpp:134:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", res.size());
                 ~~~~~~~~~~^
flood.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
flood.cpp:71: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:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
flood.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &wu[i], &wv[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 3
• Subtask 5: 0 / 10
• Subtask 6: 0 / 3
• Subtask 7: 0 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9