제출 #1104675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1104675		LinhLewLew	Park (BOI16_park)	C++17	27 / 100	198 ms	58292 KiB

park

// PhuThuyRuntime <3
// A secret makes a woman woman

#include <bits/stdc++.h>

using namespace std;

#define eb emplace_back
#define ef emplace_front
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define fo(i, l, r) for(int i = l; i <= r; i++)
#define foi(i, l, r) for(int i = l; i >= r; i--)
#define elif else if
#define el cout << "\n";
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define fi first
#define se second
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define ll long long
#define ull unsigned long long
#define pob pop_back
#define bs binary_search
#define vi vector<int>
#define vii vector<pair<int, int>>
#define getbit(i, j) ((i >> j) & 1)
#define offbit(i, j) ((1 << j) ^ i)
#define onbit(i, j) ((1 << j) | i)
const int N = 1e5 + 2;
const ll mod = 1e9 + 7;
const int inf = INT_MAX;
const int base = 31;
const long double EPS = 1e-9;
const long double pi = acos(-1.0);
int n, m, w, h;
struct person{
     ll fi, se, val;
     bool operator < (const person &other) const{
          return fi < other.fi;
     }
} a[2002];
struct tree{
     ll fi, se, val;
     bool operator < (const tree &other) const{
          return val < other.val;
     }
} b[N];
void inp(){
     cin >> n >> m >> w >> h;
     fo(i, 1, n) cin >> a[i].fi >> a[i].se >> a[i].val;
     fo(i, 1, m){
          cin >> b[i].fi >> b[i].se;
          b[i].val = i;
     }
}
struct dsu{
     int par[2 * N], sz[2 * N];
     void makeset(int u){
          par[u] = u;
          sz[u] = 1;
     }
     int findset(int u){
          return u == par[u] ? u : par[u] = findset(par[u]);
     }
     void joinset(int u, int v){
          u = findset(u);
          v = findset(v);
          if(u == v) return;
          if(sz[u] < sz[v]) swap(u, v);
          par[v] = u;
          sz[u] += sz[v];
     }
} dsu;
long long distance(int u, int v){
	return (ll)sqrt((a[u].fi - a[v].fi) * (a[u].fi - a[v].fi) + (a[u].se - a[v].se) * (a[u].se - a[v].se)) + 1;
}
vector<tree> edges;
string ans[N];
void sol(){
     sort(b + 1, b + m + 1);
     fo(i, 1, n){
          edges.push_back({i, n + 1, a[i].fi - a[i].val + 1});
		edges.push_back({i, n + 2, h - (a[i].se + a[i].val) + 1});
		edges.push_back({i, n + 3, w - (a[i].fi + a[i].val) + 1});
		edges.push_back({i, n + 4, a[i].se - a[i].val + 1});
		fo(j, i + 1, n){
               edges.push_back({i, j, distance(i, j) - a[i].val - a[j].val});
          }
     }
     fo(i, 1, n + 4) dsu.makeset(i);
     sort(all(edges));
     int j = 0;
     fo(i, 1, m){
          while(j < (int)edges.size() && edges[j].val <= b[i].fi * 2){
               dsu.joinset(edges[j].fi, edges[j].se);
               j++;
          }
          int start = b[i].se, id = b[i].val;
          ans[id] += char(start + '0');
          if (start == 1){
			if (dsu.findset(n + 4) != dsu.findset(n + 3) && dsu.findset(n + 4) != dsu.findset(n + 2) && dsu.findset(n + 1) != dsu.findset(n + 4))
                    ans[id] += '2';
			if (dsu.findset(n + 2) != dsu.findset(n + 3) && dsu.findset(n + 4) != dsu.findset(n + 2) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 1) != dsu.findset(n + 4))
                    ans[id] += '3';
			if (dsu.findset(n + 1) != dsu.findset(n + 2) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 1) != dsu.findset(n + 4))
                    ans[id] += '4';
		}
		else if (start == 2){
			if (dsu.findset(n + 1) != dsu.findset(n + 4) && dsu.findset(n + 4) != dsu.findset(n + 2) && dsu.findset(n + 4) != dsu.findset(n + 3))
                    ans[id] += '1';
			if (dsu.findset(n + 2) != dsu.findset(n + 3) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 4) != dsu.findset(n + 3))
                    ans[id] += '3';
			if (dsu.findset(n + 1) != dsu.findset(n + 2) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 2) != dsu.findset(n + 4) && dsu.findset(n + 4) != dsu.findset(n + 3))
                    ans[id] += '4';
		}
		else if (start == 3){
			if (dsu.findset(n + 1) != dsu.findset(n + 4) && dsu.findset(n + 4) != dsu.findset(n + 2) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 2) != dsu.findset(n + 3))
                    ans[id] += '1';
			if (dsu.findset(n + 3) != dsu.findset(n + 4) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 2) != dsu.findset(n + 3))
                    ans[id] += '2';
			if (dsu.findset(n + 1) != dsu.findset(n + 2) && dsu.findset(n + 2) != dsu.findset(n + 4) && dsu.findset(n + 2) != dsu.findset(n + 3))
                    ans[id] += '4';
		}
		else if (start == 4){
			if (dsu.findset(n + 4) != dsu.findset(n + 1) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 1) != dsu.findset(n + 2))
                    ans[id] += '1';
			if (dsu.findset(n + 4) != dsu.findset(n + 3) && dsu.findset(n + 4) != dsu.findset(n + 2) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 1) != dsu.findset(n + 2))
                    ans[id] += '2';
			if (dsu.findset(n + 3) != dsu.findset(n + 2) && dsu.findset(n + 2) != dsu.findset(n + 4) && dsu.findset(n + 1) != dsu.findset(n + 2))
                    ans[id] += '3';
		}
     }
     fo(i, 1, m){
          sort(all(ans[i]));
          cout << ans[i], el
     }
}
int main(){
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     inp();
     sol();
     return 0;
}

• Subtask 1: 27 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42