oj.uz

Submission #989210

# Submission time Handle Problem Language Result Execution time Memory
989210 2024-05-27T18:10:56 Z MateiKing80 Park (BOI16_park) C++14
0 / 100
 186 ms 33216 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(a) (a).begin(), (a).end()

using ld = long double;
using ll = long long;

struct DSU
{
    vector<int> papa, sz;

    DSU (int N)
    {
        papa.resize(N + 1);
        sz.resize(N + 1);
        for(int i = 1; i <= N; i ++)
            papa[i] = i, sz[i] = 1;
    }

    int real_papa(int u)
    {
        if(papa[u] == u)
            return u;
        return papa[u] = real_papa(papa[u]);
    }

    void join(int u, int v)
    {
        u = real_papa(u);
        v = real_papa(v);
        if(sz[u] < sz[v])
            swap(u, v);
        sz[u] += sz[v];
        papa[v] = u;
    }

    bool query(int u, int v)
    {
        return real_papa(u) == real_papa(v);
    }
};

struct debagat
{
    int u, v, timp;
};

struct point
{
    int x, y, r;
};

struct Query
{
    int start, obez, index;
};

bool operator < (debagat a, debagat b)
{
    return a.timp < b.timp;
}

bool operator < (Query a, Query b)
{
    return a.obez < b.obez;
}

int dist(point a, point b)
{
    ll rd = sqrtl(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y)), ok = 1;
    if(sqrtl(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y)) != (ll)sqrtl(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y)))
        ok = 1;
    rd -= a.r + b.r;
    if(rd < 0)
        rd = 0, ok = 0;
    if(rd % 2 == 1)
        ok = 1;
    rd /= 2;
    return rd + ok;
}

bool f[5][5];
string ans[200005];

int main()
{
    for(int i = 1; i < 5; i ++)
        for(int j = 1; j < 5; j ++)
            f[i][j] = true;
    int n, m, h, w;
    cin >> n >> m >> w >> h;
    vector<point> p(n + 1);
    DSU ds(n + 4);
    for(int i = 1; i <= n; i ++)
        cin >> p[i].x >> p[i].y >> p[i].r;
    vector<debagat> v;
    for(int i = 1; i <= n; i ++)
        for(int j = i + 1; j <= n; j ++)
            v.push_back({i, j, dist(p[i], p[j])});
    for(int i = 1; i <= n; i ++)
        v.push_back({i, n + 1, dist(p[i], {0, p[i].y, 0})});
    for(int i = 1; i <= n; i ++)
        v.push_back({i, n + 2, dist(p[i], {p[i].x, 0, 0})});
    for(int i = 1; i <= n; i ++)
        v.push_back({i, n + 3, dist(p[i], {w, p[i].y, 0})});
    for(int i = 1; i <= n; i ++)
        v.push_back({i, n + 4, dist(p[i], {p[i].x, h, 0})});
    sort(all(v));
    vector<Query> grasi;
    for(int i = 1; i <= m; i ++)
    {
        int l, g;
        cin >> g >> l;
        grasi.push_back({l, g, i});
    }
    sort(all(grasi));
    int pnt = 0;
    for(int i = 0; i < m; i ++)
    {
        while(pnt < v.size() && v[pnt].timp <= grasi[i].obez)
            ds.join(v[pnt].u, v[pnt].v), pnt ++;
        if(ds.query(n + 1, n + 2))
            for(int j = 1; j < 5; j ++)
                if(j != 1)
                    f[1][j] = f[j][1] = false;
        if(ds.query(n + 2, n + 3))
            for(int j = 1; j < 5; j ++)
                if(j != 2)
                    f[2][j] = f[j][2] = false;
        if(ds.query(n + 3, n + 4))
            for(int j = 1; j < 5; j ++)
                if(j != 3)
                    f[3][j] = f[j][3] = false;
        if(ds.query(n + 4, n + 1))
            for(int j = 1; j < 5; j ++)
                if(j != 4)
                    f[4][j] = f[j][4] = false;
        if(ds.query(n + 1, n + 3))
            for(int j = 1; j <= 2; j ++)
                for(int k = 1; k < 5; k ++)
                    if(j != k)
                        f[j][k] = f[k][j] = false;
        if(ds.query(n + 2, n + 4))
            for(int j = 2; j <= 3; j ++)
                for(int k = 1; k < 5; k ++)
                    if(j != k)
                        f[j][k] = f[k][j] = false;

        for(int j = 1; j < 5; j ++)
            if(f[grasi[i].start][j])
                ans[grasi[i].index] += j + '0';
    }
    for(int i = 1; i <= m; i ++)
        cout << ans[i] << '\n';
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:122:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<debagat>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         while(pnt < v.size() && v[pnt].timp <= grasi[i].obez)
      |               ~~~~^~~~~~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 32184 KB Output is correct
2 Correct 185 ms 32184 KB Output is correct
3 Correct 181 ms 31848 KB Output is correct
4 Correct 179 ms 31684 KB Output is correct
5 Correct 186 ms 32440 KB Output is correct
6 Correct 186 ms 32196 KB Output is correct
7 Incorrect 177 ms 33216 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 9420 KB Output is correct
2 Incorrect 49 ms 9616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 32184 KB Output is correct
2 Correct 185 ms 32184 KB Output is correct
3 Correct 181 ms 31848 KB Output is correct
4 Correct 179 ms 31684 KB Output is correct
5 Correct 186 ms 32440 KB Output is correct
6 Correct 186 ms 32196 KB Output is correct
7 Incorrect 177 ms 33216 KB Output isn't correct
8 Halted 0 ms 0 KB -