oj.uz

Submission #164533

# Submission time Handle Problem Language Result Execution time Memory
164533 2019-11-21T10:45:09 Z nvmdava Park (BOI16_park) C++17
0 / 100
 386 ms 35780 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 367 ms 35776 KB Output is correct
2 Correct 350 ms 35776 KB Output is correct
3 Correct 351 ms 35772 KB Output is correct
4 Correct 347 ms 35776 KB Output is correct
5 Correct 386 ms 35776 KB Output is correct
6 Correct 346 ms 35780 KB Output is correct
7 Correct 335 ms 35776 KB Output is correct
8 Incorrect 328 ms 35780 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 9196 KB Output is correct
2 Correct 91 ms 9164 KB Output is correct
3 Correct 88 ms 9132 KB Output is correct
4 Correct 90 ms 9300 KB Output is correct
5 Correct 82 ms 9196 KB Output is correct
6 Incorrect 94 ms 9236 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 35776 KB Output is correct
2 Correct 350 ms 35776 KB Output is correct
3 Correct 351 ms 35772 KB Output is correct
4 Correct 347 ms 35776 KB Output is correct
5 Correct 386 ms 35776 KB Output is correct
6 Correct 346 ms 35780 KB Output is correct
7 Correct 335 ms 35776 KB Output is correct
8 Incorrect 328 ms 35780 KB Output isn't correct
9 Halted 0 ms 0 KB -