Submission #562586

#	Time	Username	Problem	Language	Result	Execution time	Memory
562586		hoanghq2004	Fountain Parks (IOI21_parks)	C++17	45 / 100	503 ms	33808 KiB

parks

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "parks.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
//
//static void check(bool cond, string message) {
//	if (!cond) {
//		printf("%s\n", message.c_str());
//		fclose(stdout);
//		exit(0);
//	}
//}
//
//static int n;
//static bool build_called;
//static int m;
//static vector<int> _u, _v, _a, _b;
//
//void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
//	check(!build_called, "build is called more than once");
//	build_called = true;
//	m = u.size();
//	check(int(v.size()) == m, "u.size() != v.size()");
//	check(int(a.size()) == m, "u.size() != a.size()");
//	check(int(b.size()) == m, "u.size() != b.size()");
//	_u = u;
//	_v = v;
//	_a = a;
//	_b = b;
//}

const int N = 2e5 + 10;

int par[N], sz[N];

int Find(int u) {
    return (u == par[u] ? u : par[u] = Find(par[u]));
}

int Union(int u, int v) {
    if ((u = Find(u)) == (v = Find(v))) return 0;
    if (sz[u] < sz[v]) swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
    return 1;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int n = x.size();
    map <pair <int, int>, int> id;
    for (int i = 0; i < n; ++i) id[{x[i], y[i]}] = i, par[i] = i, sz[i] = 1;
    vector <tuple <int, int, int, int> > ans;
    int cnt = 0;
    auto addX = [&](int x, int y, int i, int j) {
        if (Find(i) == Find(j)) return;
        if (x + y & 2) ans.push_back({i, j, x - 1, y - 1});
        else ans.push_back({i, j, x + 1, y - 1});
        cnt += Union(i, j);
    };
    auto addY = [&](int x, int y, int i, int j) {
        if (Find(i) == Find(j)) return;
        if (x + y & 2) ans.push_back({i, j, x - 1, y + 1});
        else ans.push_back({i, j, x - 1, y - 1});
        cnt += Union(i, j);
    };
    for (int i = 0; i < n; ++i) {
        if (id.find({x[i], y[i] - 2}) != id.end()) addX(x[i], y[i], i, id[{x[i], y[i] - 2}]);
        if (id.find({x[i] - 2, y[i]}) != id.end()) addY(x[i], y[i], i, id[{x[i] - 2, y[i]}]);
    }
    assert(cnt <= n - 1);
    if (cnt != n - 1) return 0;
    vector <int> u, v, a, b;
    for (auto [_u, _v, _a, _b]: ans)
        u.push_back(_u), v.push_back(_v), a.push_back(_a), b.push_back(_b);
    build(u, v, a, b);
    return 1;
}


//int main() {
//	assert(scanf("%d", &n) == 1);
//	vector<int> x(n), y(n);
//	for (int i = 0; i < n; i++) {
//		assert(scanf("%d%d", &x[i], &y[i]) == 2);
//	}
//	fclose(stdin);
//
//	build_called = false;
//	const int possible = construct_roads(x, y);
//
//	check(possible == 0 || possible == 1, "Invalid return value of construct_roads()");
//	if (possible == 1) {
//		check(build_called, "construct_roads() returned 1 without calling build()");
//	} else {
//		check(!build_called, "construct_roads() called build() but returned 0");
//	}
//
//	printf("%d\n", possible);
//	if (possible == 1) {
//		printf("%d\n", m);
//		for (int j = 0; j < m; j++) {
//			printf("%d %d %d %d\n", _u[j], _v[j], _a[j], _b[j]);
//		}
//	}
//	fclose(stdout);
//	return 0;
//}

Compilation message (stderr)

parks.cpp: In lambda function:
parks.cpp:64:15: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   64 |         if (x + y & 2) ans.push_back({i, j, x - 1, y - 1});
      |             ~~^~~
parks.cpp: In lambda function:
parks.cpp:70:15: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   70 |         if (x + y & 2) ans.push_back({i, j, x - 1, y + 1});
      |             ~~^~~

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