oj.uz

Submission #1046401

# Submission time Handle Problem Language Result Execution time Memory
1046401 2024-08-06T13:52:39 Z LucaIlie Park (BOI16_park) C++17
0 / 100
 381 ms 27076 KB 
#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 t, 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;
const int INF = 1e9;
const int UNDEF = -INF;
circle trees[MAX_N];
vector<event> events;
DSU dsu;
int minRadius[4][4];

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;

    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;
            events.push_back( { d + 1, i, j } );
        }
    }
    for ( int i = 0; i < n; i++ ) {
        events.push_back( { (trees[i].c.x - trees[i].r) / 2 + 1, i, LEFT_SIDE } );
        events.push_back( { (w - (trees[i].c.x + trees[i].r)) / 2 + 1, i, RIGHT_SIDE } );
        events.push_back( { (trees[i].c.y - trees[i].r) / 2 + 1, i, BOTTOM_SIDE } );
        events.push_back( { (h - (trees[i].c.y + trees[i].r)) / 2 + 1, i, TOP_SIDE } );
    }

    for ( int e = 0; e < 4; e++ ) {
        for ( int f = 0; f < 4; f++ )
            minRadius[e][f] = UNDEF;
    }
    for ( int e = 0; e < 4; e++ )
        minRadius[e][e] = INF;
    sort( events.begin(), events.end(), []( event a, event b ) { return a.t < b.t; } );
    for ( event ev: events ) {
        int r = ev.t;

        for ( int e = 0; e < 4; 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 ));
            }
            if ( !isClockwisePossible && minRadius[e][(e + 1) % 4] == UNDEF )
                minRadius[e][(e + 1) % 4] = r;

            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 ));
                }
            }
            if ( !isDiagPossible && minRadius[e][(e + 2) % 4] == UNDEF )
                minRadius[e][(e + 2) % 4] = r;

            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 ));
            }
            if ( !isCounterclockwisePossible && minRadius[e][(e + 3) % 4] == UNDEF )
                minRadius[e][(e + 3) % 4] = r;
        }

       dsu.connect( ev.i, ev.j );
    }

    for ( int i = 0; i < q; i++ ) {
        int r, e;
        cin >> r >> e;
        e--;
        for ( int f = 0; f < 4; f++ ) {
            if ( r < minRadius[e][f] )
                cout << f + 1;
        }
        cout << "\n";
    }

    return 0;
}

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 25796 KB Output is correct
2 Correct 364 ms 26816 KB Output is correct
3 Correct 371 ms 25792 KB Output is correct
4 Correct 355 ms 27072 KB Output is correct
5 Correct 356 ms 26048 KB Output is correct
6 Correct 381 ms 25908 KB Output is correct
7 Correct 283 ms 27076 KB Output is correct
8 Correct 325 ms 26820 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 1172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 25796 KB Output is correct
2 Correct 364 ms 26816 KB Output is correct
3 Correct 371 ms 25792 KB Output is correct
4 Correct 355 ms 27072 KB Output is correct
5 Correct 356 ms 26048 KB Output is correct
6 Correct 381 ms 25908 KB Output is correct
7 Correct 283 ms 27076 KB Output is correct
8 Correct 325 ms 26820 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -