Submission #831896

#	Time	Username	Problem	Language	Result	Execution time	Memory
831896		nhype	Fountain Parks (IOI21_parks)	C++17	45 / 100	479 ms	116076 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
#define mp make_pair
#define X first
#define Y second
#define all(a) a.begin(),a.end()
using namespace std;
using pii = pair <int, int>;

const int maxn = 5e5 + 10;

int par [maxn];

inline int get (int x) {
	if (par[x] == x) return x;
	return par[x] = get (par[x]);
}

inline void unite (int x, int y) {
	x = get (x), y = get (y);
	par[x] = y;
}

vector <int> graph [maxn][2];
bool used [maxn][2];
vector <int> u, v, c, d;
vector <pii> xx [maxn], yy [maxn];
map <pii, int> mas;
int timer = 0;
int K [maxn], M [maxn], result [maxn];
vector <int> way = {};

inline void dfs (int v, bool B) {
	way.push_back (v);
	used[v][B] = true;
	for (int i : graph[v][B]) if (!used[i][!B]) dfs (i, !B);
}

int construct_roads (vector <int> a, vector <int> b) {
	int n = (int) a.size ();
	for (int i = 0; i < n; ++i) par[i] = i;
	vector <int> _b = a;
	sort (all (_b));
	int L = _b[0], R = _b.back ();
	for (int i = 0; i < n; ++i) xx[a[i]].push_back (mp (b[i], i)), yy[b[i]].push_back (mp (a[i], i));
	for (int i = L; i <= R; i += 2) {
		sort (all (xx[i]));
		
		int N = (int) xx[i].size ();
		for (int j = 0; j < N - 1; ++j) if (xx[i][j].X + 2 == xx[i][j + 1].X) {
			int U = xx[i][j].Y, V = xx[i][j + 1].Y;
			//cout << "! " << U << ' ' << V << '\n';
			if (get (U) == get (V)) continue;
			u.push_back (U);
			v.push_back (V);
			unite (U, V);
		}
	}
	_b = b;
	sort (all (_b));
	L = _b[0], R = _b.back ();
	for (int i = L; i <= R; i += 2) {
		sort (all (yy[i]));
		int N = (int) yy[i].size ();
		for (int j = 0; j < N - 1; ++j) if (yy[i][j].X + 2 == yy[i][j + 1].X) {
			int U = yy[i][j].Y, V = yy[i][j + 1].Y;
			if (get (U) == get (V)) continue;
			u.push_back (U);
			v.push_back (V);
			unite (U, V);
		}
	}
	if ((int) u.size () != n - 1) return 0;
	for (int i = 0; i < n - 1; ++i) {
		int m1, m2;
		if (a[u[i]] == a[v[i]]) {
			m1 = a[u[i]], m2 = b[u[i]] + b[v[i]] >> 1;
			++m1;
			if (!mas[mp (m1, m2)]) ++timer, mas[mp (m1, m2)] = timer, K[timer] = m1, M[timer] = m2;
			graph[i][0].push_back (mas[mp (m1, m2)]);
			graph[mas[mp (m1, m2)]][1].push_back (i);
			m1 -= 2;
			if (!mas[mp (m1, m2)]) ++timer, mas[mp (m1, m2)] = timer, K[timer] = m1, M[timer] = m2;
			graph[i][0].push_back (mas[mp (m1, m2)]);
			graph[mas[mp (m1, m2)]][1].push_back (i);
		} else {
			m1 = a[u[i]] + a[v[i]] >> 1, m2 = b[u[i]];
			++m2;
			if (!mas[mp (m1, m2)]) ++timer, mas[mp (m1, m2)] = timer, K[timer] = m1, M[timer] = m2;
			graph[i][0].push_back (mas[mp (m1, m2)]);
			graph[mas[mp (m1, m2)]][1].push_back (i);
			m2 -= 2;
			if (!mas[mp (m1, m2)]) ++timer, mas[mp (m1, m2)] = timer, K[timer] = m1, M[timer] = m2;
			graph[i][0].push_back (mas[mp (m1, m2)]);
			graph[mas[mp (m1, m2)]][1].push_back (i);
		}
	}
	for (int i = 0; i < timer; ++i) if (graph[i][1].size () == 1 && !used[i][1]) {
		way.clear ();
		dfs (i, 1);
		int N = (int) way.size ();
		for (int j = 0; j + 1 < (int) way.size (); j += 2) result[way[j + 1]] = way[j];
	}
	for (int i = 0; i < timer; ++i) if (!used[i][1]) {
		way.clear ();
		dfs (i, 1);
		int N = (int) way.size ();
		for (int j = 0; j + 1 < (int) way.size (); j += 2) result[way[j + 1]] = way[j];
	}
	for (int i = 0; i < n - 1; ++i) c.push_back (K[result[i]]), d.push_back (M[result[i]]);
	build (u, v, c, d);
	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:77:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |    m1 = a[u[i]], m2 = b[u[i]] + b[v[i]] >> 1;
parks.cpp:87:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |    m1 = a[u[i]] + a[v[i]] >> 1, m2 = b[u[i]];
parks.cpp:101:7: warning: unused variable 'N' [-Wunused-variable]
  101 |   int N = (int) way.size ();
      |       ^
parks.cpp:107:7: warning: unused variable 'N' [-Wunused-variable]
  107 |   int N = (int) way.size ();
      |       ^

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30