Submission #437722

#	Time	Username	Problem	Language	Result	Execution time	Memory
437722		cp_is_hard	Fountain Parks (IOI21_parks)	C++17	30 / 100	694 ms	45068 KiB

parks

#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()

#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)

using namespace std;

#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) cerr << "line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif 
#include "parks.h"
map<pii, int> mp;
set<pii> occ;
vector<pii> es;
vector<int> x, y;
vector<int> dirx = {0, 0, 2, -2};
vector<int> diry = {2, -2, 0, 0};
namespace dsu {
	int n, cnt;
	vector<int> par, rk;
	void init_(int _n) {
		n = _n, cnt = n;
		print(n, cnt);
		par.assign(n, 0);
		rk.assign(n, 0);
		rep(i, 0, n - 1) par[i] = i;
	} 
	int find_par(int x) {
		if(par[par[x]] == par[x]) return par[x];
		else return par[x] = find_par(par[x]);
	}
	void unite(int a, int b) {
		int aa = find_par(a);
		int bb = find_par(b);
		if(aa == bb) return;
		cnt --;
		if(rk[aa] > rk[bb]) par[bb] = aa;
		else if(rk[bb] > rk[aa]) par[aa] = bb;
		else rk[aa] ++, par[bb] = aa;
	}
	bool same(int a, int b) {return find_par(a) == find_par(b);}
};
int type(pii c) {
	int a = c.first, b = c.second;
	if(x[a] == x[b] && abs(y[a] - y[b]) == 2) return 1;
	else if(y[a] == y[b] && abs(x[a] - x[b]) == 2) return 2;
	else return 0;
}
int construct_roads(vector<int> _x, vector<int> _y) {
    if (x.size() == 1) {
		build({}, {}, {}, {});
        return 1;
    }
    x = _x, y = _y;
    int n = x.size();
    mp.clear(), occ.clear();
    es.clear(); 
    dsu::init_(n);
	rep(i, 0, n - 1) {
		mp[pii(x[i], y[i])] = i;
		rep(j, 0, 3) {
			pii cur = {x[i] + dirx[j], y[i] + diry[j]};
			if(mp.find(cur) == mp.end()) continue;
			es.push_back({mp[cur], i});
		} 
	}   
	vector<int> u, v, a, b;
	vector<pii> use; 
	for(auto i : es) {
		if(!dsu::same(i.first, i.second)) {
			dsu::unite(i.first, i.second);
			if(pii(x[i.first], y[i.first]) 
				> pii(x[i.second], y[i.second])) swap(i.first, i.second);
			use.push_back(i);
		}
	}
	sort(use.begin(), use.end(), [](pii a, pii b){ 
		pii aa = {x[a.first], y[a.first]};
		pii bb = {x[b.first], y[b.first]};
		if(aa == bb) return type(a) > type(b);
		return aa < bb;
	});
	if(dsu::cnt != 1) return 0;
	for(auto i : use) {
		int xx = x[i.first], yy = y[i.first];
		int tx, ty;
		if(type(i) == 1) {
			if(occ.find(pii(xx - 1, yy + 1)) == occ.end()) tx = xx - 1, ty = yy + 1;
			else tx = xx + 1, ty = yy + 1; 
		}
		else {
			if(occ.find(pii(xx + 1, yy - 1)) == occ.end()) tx = xx + 1, ty = yy - 1;
			else tx = xx + 1,ty =  yy + 1;
		}
		u.push_back(i.first);
		v.push_back(i.second);
		a.push_back(tx);
		b.push_back(ty);
		occ.insert(pii(tx,ty));
	}
	build(u, v, a, b);
    return 1;
}

Compilation message (stderr)

parks.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
parks.cpp:23:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
parks.cpp:23:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |                     ^~~~

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