oj.uz

Submission #120716

# Submission time Handle Problem Language Result Execution time Memory
120716 2019-06-25T10:10:32 Z win11905 Park (BOI16_park) C++11
100 / 100
 910 ms 25224 KB 
#include <bits/stdc++.h>
#define iii tuple<int, int, int>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int N = 2e3+10;
const int INF = 2e9+1;

int n, m, w, h;
int par[N];
int x[N], y[N], r[N];
int d[4][4];
double eps = 1e-6;

vector<pii> g[4];

void init() {
    g[1] = {{2, 3}, {0, 2}, {2, 1}};
    g[2] = {{1, 2}, {1, 3}, {0, 2}, {0, 3}};
    g[3] = {{1, 3}, {0, 1}, {1, 2}};
}

int find(int u) { return par[u] = par[u] == u ? u : find(par[u]); }

int main() {
    init();
    iota(par, par+N, 0);
    scanf("%d %d %d %d", &n, &m, &w, &h);
    vector<iii> E;
    for(int i = 0; i < n; ++i) {
        scanf("%d %d %d", x+i, y+i, r+i);
        E.emplace_back(i, n, h - y[i] - r[i]);
        E.emplace_back(i, n + 1, x[i] - r[i]);
        E.emplace_back(i, n + 2, y[i] - r[i]);
        E.emplace_back(i, n + 3, w - x[i] - r[i]);
    }
    for(int i = 0; i < n; ++i) for(int j = i+1; j < n; ++j) {
        int dist = (int)(hypot(x[i] - x[j], y[i] - y[j]))  - r[i] - r[j];
        E.emplace_back(i, j, dist);
    }
    sort(E.begin(), E.end(), [&](const iii &a, const iii &b) { return get<2>(a) < get<2>(b); });
    for(int i = 0; i < 4; ++i) for(int j = 0; j < 4; ++j) {
        if(i == j) d[i][i] = INF;
        else d[i][j] = -1;
    }
    for(auto x : E) {
        int u, v, w; tie(u, v, w) = x;
        par[find(u)] = find(v);
        for(int i = 0; i < 4; ++i) for(int j = 0; j < 4; ++j) if(i != j) {
            int dist = (j-i+4) % 4;
            for(auto z : g[dist]) {
                int a, b; tie(a, b) = z;
                a = n + ((a + i) % 4), b = n + ((b + i) % 4);
                if(find(a) == find(b) && d[i][j] == -1) d[i][j] = w;
            }
        }
    }
    for(int i = 0; i < 4; ++i) for(int j = 0; j < 4; ++j) if(d[i][j] == -1) d[i][j] = INF;
    for(int i = 0, a, b; i < m; ++i) {
        scanf("%d %d", &a, &b), b--; a *= 2;
        for(int j = 0; j < 4; ++j) if(a <= d[b][j]) printf("%d", j+1);
        printf("\n");
    }
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &n, &m, &w, &h);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", x+i, y+i, r+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:62:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b), b--; a *= 2;
         ~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 850 ms 25116 KB Output is correct
2 Correct 841 ms 25160 KB Output is correct
3 Correct 845 ms 25172 KB Output is correct
4 Correct 867 ms 25164 KB Output is correct
5 Correct 841 ms 25032 KB Output is correct
6 Correct 846 ms 25160 KB Output is correct
7 Correct 701 ms 25172 KB Output is correct
8 Correct 693 ms 25224 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1108 KB Output is correct
2 Correct 54 ms 1012 KB Output is correct
3 Correct 52 ms 1112 KB Output is correct
4 Correct 52 ms 1184 KB Output is correct
5 Correct 53 ms 1084 KB Output is correct
6 Correct 56 ms 1140 KB Output is correct
7 Correct 42 ms 632 KB Output is correct
8 Correct 43 ms 760 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 850 ms 25116 KB Output is correct
2 Correct 841 ms 25160 KB Output is correct
3 Correct 845 ms 25172 KB Output is correct
4 Correct 867 ms 25164 KB Output is correct
5 Correct 841 ms 25032 KB Output is correct
6 Correct 846 ms 25160 KB Output is correct
7 Correct 701 ms 25172 KB Output is correct
8 Correct 693 ms 25224 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 55 ms 1108 KB Output is correct
12 Correct 54 ms 1012 KB Output is correct
13 Correct 52 ms 1112 KB Output is correct
14 Correct 52 ms 1184 KB Output is correct
15 Correct 53 ms 1084 KB Output is correct
16 Correct 56 ms 1140 KB Output is correct
17 Correct 42 ms 632 KB Output is correct
18 Correct 43 ms 760 KB Output is correct
19 Correct 881 ms 25112 KB Output is correct
20 Correct 895 ms 25036 KB Output is correct
21 Correct 907 ms 25160 KB Output is correct
22 Correct 894 ms 25080 KB Output is correct
23 Correct 910 ms 25160 KB Output is correct
24 Correct 771 ms 25160 KB Output is correct