oj.uz

Submission #408796

# Submission time Handle Problem Language Result Execution time Memory
408796 2021-05-19T16:12:43 Z SirCovidThe19th Park (BOI16_park) C++14
100 / 100
 698 ms 69124 KB 
#include <bits/stdc++.h>
using namespace std;

struct pt{
    long long x, y, r;
    int border; //-1, 0, 1, 2, 3 -> not border, up, right, down, left
};
struct visitor{
    int r, e, id;
};
struct edg{
    int a, b; long double w;
};

bool operator<(const edg& a, const edg& b) {
    return (a.w < b.w);
}
bool operator<(const visitor& a, const visitor& b) {
    return (a.r < b.r);
}

int n, m, w, h;
bool cn[4][4];
vector<pt> circles; vector<edg> edges; vector<visitor> people;

vector<int> par, sz; vector<vector<bool>> group;
int find(int node){
    if (par[node] == node) return node;
    return par[node] = find(par[node]);
}
void merge(int a, int b){
    a = find(a), b = find(b);
    if (sz[a] > sz[b]) swap(a, b);
    for (int i = 0; i < 4; i++)
        group[b][i] = (group[b][i] or group[a][i]);
    for (int i = 0; i < 4-1; i++)
        for (int j = i+1; j < 4; j++)
            if (group[b][i] and group[b][j])
                cn[i][j] = true, cn[j][i] = true;
    par[a] = b; sz[a] += b;
}

long double circleDist(pt u, pt v){
    return sqrt((u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y))-(u.r+v.r);
}
long double circleBorderDist(pt u, pt v){
    if (u.border == -1) swap(u, v);
    if (u.border == 0) return h-v.y-v.r;
    if (u.border == 1) return w-v.x-v.r;
    if (u.border == 2) return v.y-v.r;
    if (u.border == 3) return v.x-v.r;
}

pair<int, int> sides[4] = {{2, 3}, {2, 1}, {0, 1}, {0, 3}};
int diag[4] = {2, 3, 0, 1};
int upDown[4] = {3, 2, 1, 0}; int rightLeft[4] = {1, 0, 3, 2};
string solve(int s){
    string res = to_string(s+1); 
    if (cn[sides[s].first][sides[s].second]) 
        return res;
    if (!cn[1][3] and !cn[sides[upDown[s]].first][sides[upDown[s]].second])
        res += to_string(upDown[s]+1);
    if (!cn[0][2] and !cn[sides[rightLeft[s]].first][sides[rightLeft[s]].second])
        res += to_string(rightLeft[s]+1);
    if (!cn[0][2] and !cn[1][3] and !cn[sides[diag[s]].first][sides[diag[s]].second])
        res += to_string(diag[s]+1);
    sort(res.begin(), res.end()); return res;
}

int main(){

    cin >> n >> m >> w >> h; circles.resize(n+4); people.resize(m);
    
    for (int i = 0; i < n; i++){
        cin >> circles[i].x >> circles[i].y >> circles[i].r; 
        circles[i].border = -1;
    }
    for (int i = 0; i < 4; i++) 
        circles[i+n] = {0, 0, 0, i};
        
    for (int i = 0; i < n+4-1; i++){
        for (int j = i+1; j < n+4; j++){
            if (circles[i].border == -1 and circles[j].border == -1)
                edges.push_back({i, j, circleDist(circles[i], circles[j])});
            else if (circles[i].border == -1 or circles[j].border == -1) 
                edges.push_back({i, j, circleBorderDist(circles[i], circles[j])});
        }
    }
    
    for (int i = 0; i < m; i++){
        cin >> people[i].r >> people[i].e; 
        people[i].e--; people[i].r *= 2; people[i].id = i;
    }

    sort(edges.begin(), edges.end());
    sort(people.begin(), people.end());

    for (int i = 0; i < n+4; i++){
        sz.push_back(1); par.push_back(i);
        group.push_back(vector<bool>(4, false)); 
        if (i >= n) group[i][i-n] = true;
    }

    memset(cn, false, sizeof(cn));
    string res[m]; int pos = 0;

    for (int i = 0; i < m; i++){
        while (pos < edges.size() and edges[pos].w < people[i].r){
            merge(edges[pos].a, edges[pos].b); pos++;
        }
        res[people[i].id] = solve(people[i].e);
    }

    for (int i = 0; i < m; i++) 
        cout<<res[i]<<endl;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         while (pos < edges.size() and edges[pos].w < people[i].r){
      |                ~~~~^~~~~~~~~~~~~~
park.cpp: In function 'long double circleBorderDist(pt, pt)':
park.cpp:52:1: warning: control reaches end of non-void function [-Wreturn-type]
   52 | }
      | ^

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 66220 KB Output is correct
2 Correct 465 ms 66132 KB Output is correct
3 Correct 439 ms 66184 KB Output is correct
4 Correct 461 ms 66204 KB Output is correct
5 Correct 449 ms 66144 KB Output is correct
6 Correct 444 ms 66308 KB Output is correct
7 Correct 452 ms 66148 KB Output is correct
8 Correct 420 ms 66120 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 6848 KB Output is correct
2 Correct 233 ms 6724 KB Output is correct
3 Correct 250 ms 6592 KB Output is correct
4 Correct 237 ms 6728 KB Output is correct
5 Correct 238 ms 6724 KB Output is correct
6 Correct 243 ms 6812 KB Output is correct
7 Correct 237 ms 6144 KB Output is correct
8 Correct 232 ms 6064 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 66220 KB Output is correct
2 Correct 465 ms 66132 KB Output is correct
3 Correct 439 ms 66184 KB Output is correct
4 Correct 461 ms 66204 KB Output is correct
5 Correct 449 ms 66144 KB Output is correct
6 Correct 444 ms 66308 KB Output is correct
7 Correct 452 ms 66148 KB Output is correct
8 Correct 420 ms 66120 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 243 ms 6848 KB Output is correct
12 Correct 233 ms 6724 KB Output is correct
13 Correct 250 ms 6592 KB Output is correct
14 Correct 237 ms 6728 KB Output is correct
15 Correct 238 ms 6724 KB Output is correct
16 Correct 243 ms 6812 KB Output is correct
17 Correct 237 ms 6144 KB Output is correct
18 Correct 232 ms 6064 KB Output is correct
19 Correct 670 ms 69052 KB Output is correct
20 Correct 670 ms 69124 KB Output is correct
21 Correct 689 ms 69124 KB Output is correct
22 Correct 671 ms 68956 KB Output is correct
23 Correct 698 ms 69048 KB Output is correct
24 Correct 683 ms 69008 KB Output is correct