This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define BOTTOM_SIDE n
#define RIGHT_SIDE n + 1
#define TOP_SIDE n + 2
#define LEFT_SIDE n + 3
#define BOTTOM_LEFT 0
#define BOTTOM_RIGHT 1
#define TOP_RIGHT 2
#define TOP_LEFT 3
using namespace std;
struct point {
int x, y;
};
int dist( point a, point b ) {
return sqrt( (long long)(a.x - b.x) * (a.x - b.x) + (long long)(a.y - b.y) * (a.y - b.y) );
}
struct circle {
point c;
int r;
};
struct event {
int i, j;
};
struct query {
int e, r;
bool ans[4];
};
struct DSU {
int n;
vector<int> parent;
void init( int _n ) {
n = _n;
parent.resize( n );
for ( int i = 0; i < n; i++ )
parent[i] = i;
}
int findRoot( int v ) {
if ( parent[v] == v )
return v;
parent[v] = findRoot( parent[v] );
return parent[v];
}
void connect( int u, int v ) {
u = findRoot( u );
v = findRoot( v );
parent[u] = v;
}
bool areConnected( int u, int v ) {
return findRoot( u ) == findRoot( v );
}
};
const int MAX_N = 2e3;
const int MAX_Q = 1e5;
circle trees[MAX_N];
query queries[MAX_Q];
map<int, vector<event>> eventsByTime;
map<int, vector<int>> queriesByTime;
DSU dsu;
int main() {
int n, q, w, h;
cin >> n >> q >> w >> h;
for ( int i = 0; i < n; i++ )
cin >> trees[i].c.x >> trees[i].c.y >> trees[i].r;
for ( int i = 0; i < q; i++ ) {
cin >> queries[i].r >> queries[i].e;
queries[i].e--;
for ( int e = 0; e < 4; e++ )
queries[i].ans[e] = (e == queries[i].e);
queriesByTime[queries[i].r].push_back( i );
}
dsu.init( n + 4 );
for ( int i = 0; i < n; i++ ) {
for ( int j = i + 1; j < n; j++ ) {
int d = (dist( trees[i].c, trees[j].c ) - trees[i].r - trees[j].r) / 2;
if ( d < queries[0].r )
dsu.connect( i, j );
//else
// eventsByTime[d].push_back( { i, j } );
}
}
for ( int i = 0; i < n; i++ ) {
eventsByTime[(trees[i].c.x - trees[i].r) / 2].push_back( { i, LEFT_SIDE } );
eventsByTime[(w - (trees[i].c.x + trees[i].r)) / 2].push_back( { i, RIGHT_SIDE } );
eventsByTime[(trees[i].c.y - trees[i].r) / 2].push_back( { i, BOTTOM_SIDE } );
eventsByTime[(h - (trees[i].c.y + trees[i].r)) / 2].push_back( { i, TOP_SIDE } );
}
vector<int> relevantTimes;
for ( auto p: eventsByTime )
relevantTimes.push_back( p.first );
for ( auto p: queriesByTime )
relevantTimes.push_back( p.first );
sort( relevantTimes.begin(), relevantTimes.end() );
relevantTimes.resize( unique( relevantTimes.begin(), relevantTimes.end() ) - relevantTimes.begin() );
for ( int t: relevantTimes ) {
for ( int ind: queriesByTime[t] ) {
int e = queries[ind].e;
bool isClockwisePossible = true;
for ( int i = 0; i < 4; i++ ) {
int s1 = n + e, s2 = n + i;
if ( s1 != s2 )
isClockwisePossible &= (!dsu.areConnected( s1, s2 ));
}
queries[ind].ans[(e + 1) % 4] = isClockwisePossible;
bool isDiagPossible = true;
for ( int i = 0; i < 2; i++ ) {
for ( int j = 2; j < 4; j++ ) {
int s1 = n + (e + i) % 4, s2 = n + (e + j) % 4;
if ( s1 != s2 )
isDiagPossible &= (!dsu.areConnected( s1, s2 ));
}
}
queries[ind].ans[(e + 2) % 4] = isDiagPossible;
bool isCounterclockwisePossible = true;
for ( int i = 0; i < 4; i++ ) {
int s1 = n + (e + 3) % 4, s2 = n + i;
if ( s1 != s2 )
isCounterclockwisePossible &= (!dsu.areConnected( s1, s2 ));
}
queries[ind].ans[(e + 3) % 4] = isCounterclockwisePossible;
}
for ( event e: eventsByTime[t] )
dsu.connect( e.i, e.j );
}
for ( int i = 0; i < q; i++ ) {
for ( int e = 0; e < 4; e++ ) {
if ( queries[i].ans[e] )
cout << (e + 1);
}
cout << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |