oj.uz

Submission #1046433

# Submission time Handle Problem Language Result Execution time Memory
1046433 2024-08-06T14:28:15 Z LucaIlie Park (BOI16_park) C++17
100 / 100
 196 ms 29596 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, i;
    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];
vector<event> events;
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].i = i;
        queries[i].e--;
        for ( int e = 0; e < 4; e++ )
            queries[i].ans[e] = (e == queries[i].e);
    }

    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, 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 } );
    }

    sort( queries, queries + q, []( query a, query b) { return a.r < b.r; } );
    sort( events.begin(), events.end(), []( event a, event b) { return a.t < b.t; } );
    int indEv = 0;
    for ( int ind = 0; ind < q; ind++ ) {
        while ( indEv < events.size() && events[indEv].t < queries[ind].r ) {
            dsu.connect( events[indEv].i, events[indEv].j );
            indEv++;
        }

        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;
    }

    sort( queries, queries + q, []( query a, query b) { return a.i < b.i; } );
    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;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         while ( indEv < events.size() && events[indEv].t < queries[ind].r ) {
      |                 ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 25280 KB Output is correct
2 Correct 147 ms 25404 KB Output is correct
3 Correct 145 ms 26304 KB Output is correct
4 Correct 146 ms 25280 KB Output is correct
5 Correct 144 ms 25784 KB Output is correct
6 Correct 143 ms 25324 KB Output is correct
7 Correct 133 ms 26052 KB Output is correct
8 Correct 141 ms 27328 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3412 KB Output is correct
2 Correct 48 ms 3404 KB Output is correct
3 Correct 50 ms 3448 KB Output is correct
4 Correct 49 ms 3412 KB Output is correct
5 Correct 50 ms 3408 KB Output is correct
6 Correct 48 ms 3348 KB Output is correct
7 Correct 46 ms 2900 KB Output is correct
8 Correct 55 ms 2896 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 25280 KB Output is correct
2 Correct 147 ms 25404 KB Output is correct
3 Correct 145 ms 26304 KB Output is correct
4 Correct 146 ms 25280 KB Output is correct
5 Correct 144 ms 25784 KB Output is correct
6 Correct 143 ms 25324 KB Output is correct
7 Correct 133 ms 26052 KB Output is correct
8 Correct 141 ms 27328 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 55 ms 3412 KB Output is correct
12 Correct 48 ms 3404 KB Output is correct
13 Correct 50 ms 3448 KB Output is correct
14 Correct 49 ms 3412 KB Output is correct
15 Correct 50 ms 3408 KB Output is correct
16 Correct 48 ms 3348 KB Output is correct
17 Correct 46 ms 2900 KB Output is correct
18 Correct 55 ms 2896 KB Output is correct
19 Correct 195 ms 29384 KB Output is correct
20 Correct 192 ms 28308 KB Output is correct
21 Correct 191 ms 28612 KB Output is correct
22 Correct 189 ms 29596 KB Output is correct
23 Correct 196 ms 29372 KB Output is correct
24 Correct 177 ms 28604 KB Output is correct