oj.uz

답안 #1013874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1013874 2024-07-04T07:07:02 Z pan Park (BOI16_park) C++17
100 / 100
 716 ms 67988 KB 
#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#include <initializer_list>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
typedef pair<pi, pi> piii;

// UFDS
ll par[5005], siz[5005];
ll find(ll x){return ((par[x]==x)?x:par[x] = find(par[x]));}
void unite(ll x, ll y)
{ 
	x= find(x), y = find(y);
	if (siz[x] < siz[y]) swap(x,y);
	siz[x] += siz[y];
	par[y] = x;
}
ll lable = 4;
ll x[5005], y[5005], r[5005];
vector<pii> q;
string ans[500005];

vector<pii> upd;

bool compare(pii a, pii b){ return a.f  < b.f;}

void update(ll idx1, ll idx2)
{
	ll xx = abs(x[idx1]-x[idx2]), yy = abs(y[idx1] - y[idx2]);
	ll sq = xx*xx + yy*yy;
	ll lo = 0, hi = 3e9;
	//show(hi*hi);
	while (lo!=hi)
	{
		ll mid = (lo+hi+1)/2;
		if (mid*mid <= sq) lo = mid;
		else hi = mid-1;
	}
	ll dist =  lo - r[idx1] - r[idx2];
	upd.pb(mp(dist, mp(idx1	, idx2)));
}


int main()
{
	ll n,m , w, h;
	input4(n, m, w, h);
	q.resize(m);
	for (ll i=1; i<n+5; ++i) par[i] = i, siz[i]=1;
	//for (ll i=1; i<=4; ++i) minx[i] = miny[i] = INF, maxx[i], maxy[i] = -INF;
	for (ll i=0; i<n; ++i) 
	{
		input3(x[i+5], y[i+5], r[i+5]);
		//minx[i+5] = maxx[i+5] = x[i+5];
		//miny[i+5] = maxy[i+5] = y[i+5];
		// Reset
		x[1] =  x[3] = x[i+5];
		y[1] = 0, y[3] = h;
		x[2] = w, x[4] = 0;
		y[2] = y[4] = y[i+5];
		r[1] = r[2] = r[3] =r[4] = 0;
		// Add edges
		for (ll j=1; j<=4; ++j) update(j, i+5);
	}
	for (ll i=5; i<n+5; ++i) for (ll j=i+1; j<n+5; ++j) update(i, j);
	for (ll i=0; i<m; ++i) {input2(q[i].f, q[i].s.f); q[i].s.s = i;}
	sort(all(upd), compare);
	sort(all(q), compare);
	ll idx = -1;
	for (pii u: q)
	{
		//show(u.s.s);
		while (idx + 1 < upd.size() && upd[idx+1].f< u.f*2)
		{
			idx++;
			unite(upd[idx].s.f, upd[idx].s.s);
			//show3(upd[idx].f, upd[idx].s.f, upd[idx].s.s);
		}
		vector<vector<ll> > dp(5, vector<ll> (5, 0));
		vector<vector<ll> > dp2(5, vector<ll> (5, 1));
		for (ll i=1; i<=4; ++i) for (ll j=1; j<=4; ++j) {if (find(i)==find(j)) dp[i][j]=1;}
		// dist = 1
		for (ll i=1; i<=4; ++i)
		{
			ll nxt = (i==4)?1:i+1;
			if (dp[i][nxt]) for (ll j=1; j<=4; ++j) if (nxt!=j) dp2[j][nxt] = dp2[nxt][j] = 0;
		}
		// dist = 2
		ll aa[2] = {1, 4}, bb[2] = {2,3};
		if (dp[1][3]) for (ll j: aa) for (ll i: bb) if (i!=j) dp2[j][i] = dp2[i][j] = 0;
		if (dp[2][4]) for (ll j=1; j<=2; ++j) for (ll i=3; i<=4; ++i) if (i!=j) dp2[j][i] = dp2[i][j] = 0;
		ans[u.s.s] = "";
		for (ll i=1; i<=4; ++i) if (dp2[u.s.f][i]) ans[u.s.s] += to_string(i);
		
	}
	for (ll i=0; i<m; ++i) cout << ans[i] << endl;
	
	
	return 0;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:103:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   while (idx + 1 < upd.size() && upd[idx+1].f< u.f*2)
      |          ~~~~~~~~^~~~~~~~~~~~
park.cpp:16:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:77:2: note: in expansion of macro 'input4'
   77 |  input4(n, m, w, h);
      |  ^~~~~~
park.cpp:15:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 | #define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:83:3: note: in expansion of macro 'input3'
   83 |   input3(x[i+5], y[i+5], r[i+5]);
      |   ^~~~~~
park.cpp:14:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
park.cpp:96:26: note: in expansion of macro 'input2'
   96 |  for (ll i=0; i<m; ++i) {input2(q[i].f, q[i].s.f); q[i].s.s = i;}
      |                          ^~~~~~

Subtask #1
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 645 ms 65444 KB Output is correct
2 Correct 607 ms 65412 KB Output is correct
3 Correct 631 ms 65412 KB Output is correct
4 Correct 650 ms 65668 KB Output is correct
5 Correct 659 ms 65420 KB Output is correct
6 Correct 629 ms 65416 KB Output is correct
7 Correct 629 ms 65416 KB Output is correct
8 Correct 578 ms 65420 KB Output is correct
9 Correct 8 ms 16216 KB Output is correct
10 Correct 8 ms 16080 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 20428 KB Output is correct
2 Correct 70 ms 20380 KB Output is correct
3 Correct 72 ms 20168 KB Output is correct
4 Correct 71 ms 20396 KB Output is correct
5 Correct 69 ms 20424 KB Output is correct
6 Correct 82 ms 20384 KB Output is correct
7 Correct 63 ms 19792 KB Output is correct
8 Correct 85 ms 19896 KB Output is correct

Subtask #3
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 645 ms 65444 KB Output is correct
2 Correct 607 ms 65412 KB Output is correct
3 Correct 631 ms 65412 KB Output is correct
4 Correct 650 ms 65668 KB Output is correct
5 Correct 659 ms 65420 KB Output is correct
6 Correct 629 ms 65416 KB Output is correct
7 Correct 629 ms 65416 KB Output is correct
8 Correct 578 ms 65420 KB Output is correct
9 Correct 8 ms 16216 KB Output is correct
10 Correct 8 ms 16080 KB Output is correct
11 Correct 65 ms 20428 KB Output is correct
12 Correct 70 ms 20380 KB Output is correct
13 Correct 72 ms 20168 KB Output is correct
14 Correct 71 ms 20396 KB Output is correct
15 Correct 69 ms 20424 KB Output is correct
16 Correct 82 ms 20384 KB Output is correct
17 Correct 63 ms 19792 KB Output is correct
18 Correct 85 ms 19896 KB Output is correct
19 Correct 690 ms 67988 KB Output is correct
20 Correct 716 ms 67976 KB Output is correct
21 Correct 676 ms 67980 KB Output is correct
22 Correct 690 ms 67980 KB Output is correct
23 Correct 653 ms 67980 KB Output is correct
24 Correct 657 ms 67980 KB Output is correct