oj.uz

Submission #164535

# Submission time Handle Problem Language Result Execution time Memory
164535 2019-11-21T10:47:37 Z nvmdava Park (BOI16_park) C++17
0 / 100
 383 ms 35904 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007LL
#define N 2005

vector<pair<double, pair<int, int > > > dist, q;

int p[N];
double x[N], y[N], r[N];

inline double sq(double w){
    return w * w;
}

int find(int v){
    return v == p[v] ? v : p[v] = find(p[v]);
}

void unite(int v, int u){
    v = find(v);
    u = find(u);
    p[v] = u;
}

vector<int> ans[100005];

bool check(int v, int u){
    if(v == u) return 1;
    find(1);
    find(2);
    find(3);
    find(4);
    if(v > u) swap(v, u);
    swap(v, u);
    if(v == 1 && p[1] == p[2])
        return 0;
    if(v == 2 && p[2] == p[3])
        return 0;
    if(v == 3 && p[4] == p[3])
        return 0;
    if(v == 4 && p[4] == p[1])
        return 0;
    swap(v, u);
    if(v == 1 && p[1] == p[2])
        return 0;
    if(v == 2 && p[2] == p[3])
        return 0;
    if(v == 3 && p[4] == p[3])
        return 0;
    if(v == 4 && p[4] == p[1])
        return 0;
    if(v == 1){
        if(u == 2){
            if(p[2] == p[4])
                return 0;
            return 1;
        }
        if(u == 3){
            if(p[2] == p[4] || p[1] == p[3])
                return 0;
            return 1;
        }
        if(u == 4){
            if(p[1] == p[3])
                return 0;
            return 1;
        }
    }
    if(v == 3){
        if(u == 4){
            if(p[2] == p[4])
                return 0;
            return 1;
        }
    }
    if(v == 2){
        if(u == 3){
            if(p[1] == p[3])
                return 0;
            return 1;
        }
        if(u == 4){
            if(p[1] == p[3] || p[2] == p[4])
                return 0;
            return 1;
        }
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m, w, h;
    cin>>n>>m;
    cin>>w>>h;
    for(int i = n + 4; i > 0; --i)
        p[i] = i;
    for(int i = n + 4; i > 4; --i){
        cin>>x[i]>>y[i]>>r[i];
        for(int j = n + 4; j > i; --j){
            double d = sqrt(sq(x[i] - x[j]) + sq(y[i] - y[j]));
            d -= r[i] + r[j];
            dist.push_back({d, {i, j}});
        }
        dist.push_back({x[i] - r[i], {1, i}});
        dist.push_back({y[i] - r[i], {2, i}});
        dist.push_back({w - x[i] - r[i], {3, i}});
        dist.push_back({h - y[i] - r[i], {4, i}});
    }
    sort(dist.rbegin(), dist.rend());
    for(int i = 1; i <= m; i++){
        int R, E;
        cin>>R>>E;
        R *= 2;
        q.push_back({R, {i, E}});
    }
    sort(q.begin(), q.end());
    for(auto& Q : q){
        while(!dist.empty() && dist.back().ff < Q.ff){
            unite(dist.back().ss.ff, dist.back().ss.ss);
            dist.pop_back();
        }
        for(int i = 1; i <= 4; i++){
            if(check(i, Q.ss.ss)){
                ans[Q.ss.ff].push_back(i);
            }
        }
    }

    for(int i = 1; i <= m; i++){
        sort(ans[i].begin(), ans[i].end());
        for(auto& x : ans[i])
            cout<<x;
        cout<<'\n';
    }
}

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 35776 KB Output is correct
2 Correct 350 ms 35648 KB Output is correct
3 Correct 383 ms 35684 KB Output is correct
4 Correct 376 ms 35780 KB Output is correct
5 Correct 349 ms 35648 KB Output is correct
6 Correct 346 ms 35904 KB Output is correct
7 Correct 332 ms 35648 KB Output is correct
8 Correct 326 ms 35648 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Incorrect 4 ms 2680 KB Output isn't correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 8296 KB Output is correct
2 Correct 87 ms 8172 KB Output is correct
3 Correct 89 ms 8116 KB Output is correct
4 Correct 97 ms 8040 KB Output is correct
5 Correct 86 ms 8172 KB Output is correct
6 Correct 87 ms 8172 KB Output is correct
7 Incorrect 115 ms 9072 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 35776 KB Output is correct
2 Correct 350 ms 35648 KB Output is correct
3 Correct 383 ms 35684 KB Output is correct
4 Correct 376 ms 35780 KB Output is correct
5 Correct 349 ms 35648 KB Output is correct
6 Correct 346 ms 35904 KB Output is correct
7 Correct 332 ms 35648 KB Output is correct
8 Correct 326 ms 35648 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Incorrect 4 ms 2680 KB Output isn't correct