oj.uz

Submission #307428

# Submission time Handle Problem Language Result Execution time Memory
307428 2020-09-28T05:46:13 Z xyzyzl Park (BOI16_park) C++14
100 / 100
 584 ms 69716 KB 
// Time:
// Algorithms: 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // pbds
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

#pragma GCC optimize("O3")

using namespace __gnu_pbds;
using namespace std;

#define MAXN 200005

#define FOR(i, n) for (int i = 0; i < n; i++)
#define FORR(j, i, n) for (int i = j; i < n; i++)
#define FORD(i, n) for (int i = n - 1; i >= 0; i--)
#define F1R(i, n) for (int i = 1; i <= n; i++)
#define F1RD(i, n) for (int i = n; i >= 1; i--)
#define pb push_back
#define mp make_pair
#define endl '\n'
#define DUEHOANG                  \
	ios_base::sync_with_stdio(0); \
	cin.tie(NULL);                \
	cout.tie(NULL)

#define fileio(in, out)      \
	freopen(in, "r", stdin); \
	freopen(out, "w", stdout);

#define ll long long
#define int ll
#define MOD (1e9*1)+7
#define MOD2 998244353
#define INF (1e9*1)+5

typedef set<int> si;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<int, pii> iii;
typedef vector<pii> vii;
typedef vector<iii> viii;
typedef priority_queue<int> pqi;
typedef stack<int> sti;
typedef queue<int> qi;
typedef deque<int> di;
typedef map<int, int> mii;
// ordered_set
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> os;
#define f first
#define s second

#define LEFT(x) 2 * x
#define RIGHT(x) 2 * x + 1

#define bitinc(x) x&-x

const int MAX(int &a, int b)
{
	return a = max(a, b); 
}
const int MIN(int &a, int b)
{
	return a = min(a, b); 
}

int n, m, p[2010], sz[2010];
ll w, h;
iii pts[2010], vs[100010];

int find_set(int i)
{
    return (p[i] == i) ? i : (p[i] = find_set(p[i]));
}

bool union_set(int i, int j)
{
    int x = find_set(i);
    int y = find_set(j);
    if (x == y)
        return false;
    p[x] = p[y] = x;
    sz[x] += sz[y];
    return true;
}

void init()
{
    for(int i = 0; i < 2005; i++) p[i] = i;
    for(int i = 0; i < 2005; i++) sz[i] = 1;
}

double dist(pii a, pii b)
{
	return sqrt((a.f-b.f)*(a.f-b.f) + (a.s-b.s)*(a.s-b.s));
}

void solve()
{
	cin >> n >> m;
	cin >> w >> h;
	FOR(i, n)
	{
		cin >> pts[i].s.f >> pts[i].s.s >> pts[i].f;
	}
	FOR(i, m)
	{
		int r, c;
		cin >> r >> c;
		vs[i] = mp(r*2, mp(c-1, i));
	}
	vector<pair<long double, pair<int, int> > > eg;
	FOR(i, n)
	{
		FORR(i+1,j,n)
		{
			eg.pb(mp(dist(pts[i].s, pts[j].s) - pts[i].f - pts[j].f, mp(i+4, j+4)));
		}
	}
	FOR(i, n)
	{
		eg.pb(mp(dist(pts[i].s, mp(0, pts[i].s.s)) - pts[i].f, mp(i+4, 0)));
		eg.pb(mp(dist(pts[i].s, mp(pts[i].s.f, 0)) - pts[i].f, mp(i+4, 1)));
		eg.pb(mp(dist(pts[i].s, mp(w, pts[i].s.s)) - pts[i].f, mp(i+4, 2)));
		eg.pb(mp(dist(pts[i].s, mp(pts[i].s.f, h)) - pts[i].f, mp(i+4, 3)));
	}
	sort(eg.begin(), eg.end());
	sort(vs, vs+m);
	init();
	int ind = 0;
	bool bad[m][4];
	bool C[4][4];
	memset(bad, 0, sizeof bad);
	for(auto e : eg)
	{
		while(ind < m && vs[ind].f <= e.f)
		{
			memset(C, 0, sizeof C);
			FOR(i, 4)
			{
				C[i][i] = 1;
				FORR(i+1, j, 4)
				{
					C[i][j] = find_set(i) == find_set(j);
					C[j][i] = C[i][j];
				}
			}
			iii cur = vs[ind];
			FOR(i, 4)
			{
				if(cur.s.f == i) continue;
				if(C[cur.s.f][(cur.s.f+1)%4] || C[i][(i+1)%4])
				{
					// cerr << "oh" << endl;
					bad[cur.s.s][i] = 1;
				}
				bool vblock = C[1][3];
				bool hblock = C[0][2];
				if(abs(cur.s.f - i) == 2)
				{
					// cerr << "my" << endl;
					if(vblock || hblock) bad[cur.s.s][i] = 1;
				} else if(cur.s.f + i == 3)
				{
					// cerr << "fucking" << endl;
					if(hblock) bad[cur.s.s][i] = 1;
				} else 
				{
					// cerr << "god" << endl;
					if(vblock) bad[cur.s.s][i] = 1;
				}
			}
			ind++;
			if(ind >= m) break;
		}
		union_set(e.s.f, e.s.s);
	}
	FOR(i, m)
	{
		FOR(j, 4)
		{
			if(!bad[i][j]) cout << (j+1);
		}
		cout << endl;
	}
}

signed main()
{
	DUEHOANG;
	int t = 1;
	// cin >> t; // uncomment if it's multitest
	while(t--)
	{
		solve();
	}
	
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 66204 KB Output is correct
2 Correct 552 ms 66204 KB Output is correct
3 Correct 530 ms 66204 KB Output is correct
4 Correct 546 ms 66204 KB Output is correct
5 Correct 539 ms 66208 KB Output is correct
6 Correct 545 ms 66204 KB Output is correct
7 Correct 507 ms 66364 KB Output is correct
8 Correct 512 ms 66356 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 4336 KB Output is correct
2 Correct 51 ms 5232 KB Output is correct
3 Correct 52 ms 5260 KB Output is correct
4 Correct 51 ms 5360 KB Output is correct
5 Correct 51 ms 5364 KB Output is correct
6 Correct 54 ms 5356 KB Output is correct
7 Correct 46 ms 4600 KB Output is correct
8 Correct 45 ms 4600 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 66204 KB Output is correct
2 Correct 552 ms 66204 KB Output is correct
3 Correct 530 ms 66204 KB Output is correct
4 Correct 546 ms 66204 KB Output is correct
5 Correct 539 ms 66208 KB Output is correct
6 Correct 545 ms 66204 KB Output is correct
7 Correct 507 ms 66364 KB Output is correct
8 Correct 512 ms 66356 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 54 ms 4336 KB Output is correct
12 Correct 51 ms 5232 KB Output is correct
13 Correct 52 ms 5260 KB Output is correct
14 Correct 51 ms 5360 KB Output is correct
15 Correct 51 ms 5364 KB Output is correct
16 Correct 54 ms 5356 KB Output is correct
17 Correct 46 ms 4600 KB Output is correct
18 Correct 45 ms 4600 KB Output is correct
19 Correct 584 ms 69612 KB Output is correct
20 Correct 577 ms 69532 KB Output is correct
21 Correct 584 ms 69716 KB Output is correct
22 Correct 581 ms 69568 KB Output is correct
23 Correct 575 ms 69564 KB Output is correct
24 Correct 547 ms 69660 KB Output is correct